Chef has a string S consisting only of English lowercase letters (a - z). However, Hitesh does not like it and wants it to be reversed.

Hitesh wonders what is the minimum number of operations required to reverse the string S using the following operation:
Select any i such that 1 ≤ i ≤ \lvert S \rvert and remove S_{i} from its original position and append it to the end of the string (i.e. shift any character to the end of the string). 

For e.g. if S = abcde and we apply operation on i = 2, then S becomes acdeb.

Help Hitesh find the minimum number of operations required to reverse S.

It is guaranteed that it is possible to reverse the string in a finite number of operations.

------ Input Format ------ 

-   The first line of input contains a single integer  T, denoting the number of test cases. The description of  T  test cases follows.
-   Each test case consists of a single line containing the string S.

------ Output Format ------ 

For each test case, output the minimum number of operations required to reverse the string S.

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$1  ≤ \lvert S \rvert ≤ 10^{5}$
- Sum of $\lvert S \rvert$ over all testcases does not exceed $2 \cdot 10^{5}$.  

----- Sample Input 1 ------ 
2
abdeba
codechef
----- Sample Output 1 ------ 
3
7
----- explanation 1 ------ 
- Test case-1: Following steps can be performed:
1.  $abdeba \to  abebad$
2.  $abebad \to abeadb$
3.  $abeadb \to  abedba$
- Test case-2: following steps can be performed:
1.  $codechef \to  codechfe$
2.  $codechfe \to codecfeh$
3.  $codecfeh \to codefehc$
4.  $codefehc \to  codfehce$
5.  $codfehce \to cofehced$
6.  $cofehced \to cfehcedo$
7.  $cfehcedo \to fehcedoc$

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	old_s = list(input())
	r = old_s[::-1]
	i = 0
	j = 0
	n = len(old_s)
	while j < n:
		if old_s[j] == r[i]:
			i += 1
		j += 1
	print(n - i)


def ip():
	return input()
for tastcas in range(int(input())):
	old_s = list(input())
	new_s = old_s.copy()
	new_s.reverse()
	i = j = 0
	n = len(old_s)
	while j < n:
		if old_s[j] == new_s[i]:
			i += 1
		j += 1
	print(n - i)


t = int(input())
for _ in range(t):
	old_s = list(input())
	new_s = old_s.copy()
	new_s.reverse()
	i = 0
	j = 0
	n = len(old_s)
	while j < n:
		if old_s[j] == new_s[i]:
			i += 1
		j += 1
	print(n - i)


t = int(input())
while t > 0:
	t -= 1
	s = input()
	n = len(s)
	i = 0
	j = n - 1
	ans = 0
	while i < n:
		if s[i] == s[j]:
			j -= 1
		else:
			ans += 1
		i += 1
	print(ans)


t = int(input())
for i in range(t):
	s = input()
	r = s[::-1]
	(a, b) = (0, 0)
	ans = 0
	while a < len(s):
		if r[b] == s[a]:
			b += 1
		else:
			ans += 1
		a += 1
	print(ans)


for _ in range(int(input())):
	s = input()
	rev = s[::-1]
	(i, j) = (0, 0)
	ans = 0
	while i < len(s):
		if rev[j] == s[i]:
			j += 1
		else:
			ans += 1
		i += 1
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	r = s[::-1]
	i = 0
	j = 0
	x = 0
	while i < len(s) and j < len(r):
		if s[i] == r[j]:
			i += 1
			j += 1
			x += 1
		else:
			i += 1
	print(len(s) - x)


import math
test = int(input())
for _ in range(test):
	string = input()
	i = 0
	j = 0
	rev_string = string[::-1]
	count = 0
	while i < len(string):
		if string[i] == rev_string[j]:
			j += 1
		else:
			count += 1
		i += 1
	print(count)


import math
for _ in range(int(input())):
	s = input()
	i = 0
	j = 0
	r = s[::-1]
	c = 0
	while i < len(s):
		if s[i] == r[j]:
			j += 1
		else:
			c += 1
		i += 1
	print(c)


for i in range(int(input())):
	x = input()
	rev = x[::-1]
	i = 0
	j = 0
	ans = 0
	while i < len(x):
		if x[i] == rev[j]:
			i += 1
			j += 1
		else:
			i += 1
			ans += 1
	print(ans)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (10 ** 9 + 7, 998244353)

def sieve(MAXN):
	prime = [True] * (MAXN + 10)
	(prime[0], prime[1]) = [False] * 2
	for i in range(2, int(math.sqrt(MAXN + 1)) + 5):
		if prime[i] == True:
			for j in range(i * i, MAXN + 5, i):
				prime[j] = False
	return prime

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = int(input())
	for __ in range(how_much_noob_I_am):
		s = inp()
		p = s[::-1]
		if s == p:
			print(0)
			continue
		j = 0
		for i in range(len(s)):
			if s[i] == p[j]:
				j += 1
		print(len(s) - j)
main()


for t in range(int(input())):
	a = input()
	l = len(a)
	rev = a[::-1]
	(i, j) = (0, 0)
	while i < l:
		if a[i] == rev[j]:
			j += 1
		i += 1
	print(l - j)


import math, sys

def input():
	return sys.stdin.readline().rstrip('\r\n')
tcs = int(input())
for _ in range(tcs):
	wrd1 = input()
	wrd2 = wrd1
	wrd1 = wrd1[::-1]
	sz1 = len(wrd1)
	sz2 = len(wrd2)
	ans = 0
	(i, j) = (sz2 - 1, sz2 - 1)
	while i > -1:
		while i > -1 and wrd1[i] != wrd2[j]:
			i -= 1
			ans += 1
		if i > -1:
			i -= 1
			j -= 1
	sys.stdout.write(str(ans) + '\n')


T = int(input())
for i in range(T):
	s = input()
	n = len(s) - 1
	m = len(s)
	r = s[::-1]
	j = f = 0
	for i in range(m):
		if s[i] != r[j]:
			f += 1
		else:
			j += 1
	print(f)


for T in range(int(input())):
	A = input()
	l = len(A)
	revA = A[::-1]
	(i, j) = (0, 0)
	while i < l:
		if A[i] == revA[j]:
			j += 1
		i += 1
	print(l - j)


for _ in range(int(input())):
	s = input()
	b = s[::-1]
	j = 0
	ans = 0
	for i in range(len(s)):
		if s[i] == b[j]:
			j += 1
		else:
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	answer = 0
	rev = s[::-1]
	n = len(s)
	j = n - 1
	i = n - 1
	while i >= 0:
		while i >= 0 and rev[i] != s[j]:
			i -= 1
			answer += 1
		if i >= 0:
			i -= 1
			j -= 1
	print(answer)


def rev(A):
	l = len(A)
	B = []
	for i in range(l - 1, -1, -1):
		B.append(A[i])
	return B
test = int(input())
for case in range(test):
	s = str(input())
	a = [n for n in s]
	ra = rev(a)
	count = 0
	l = len(a)
	(i, j) = (0, 0)
	while i < l:
		if a[i] == ra[j]:
			j = j + 1
		else:
			count = count + 1
		i = i + 1
	print(count)


for _ in range(int(input())):
	string = input()
	rev = string[::-1]
	(i, j) = (0, 0)
	while i < len(string):
		if rev[j] == string[i]:
			j += 1
		i += 1
	print(len(string) - j)


caseCount = int(input())
for i in range(caseCount):
	inputString = input()
	sLen = len(inputString)
	i = 0
	j = sLen - 1
	moves = 0
	while i < sLen:
		if inputString[i] == inputString[j]:
			j -= 1
		else:
			moves += 1
		i += 1
	print(moves)


from collections import defaultdict
import sys
input = sys.stdin.readline
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	string = input().strip()
	target = string[::-1]
	removed_count = defaultdict(int)
	num_removed = 0
	length = len(string)
	i_string = 0
	i_target = 0
	while i_string < length:
		if string[i_string] != target[i_target]:
			i_target -= 1
			num_removed += 1
		i_string += 1
		i_target += 1
	print(num_removed)


def calc(s):
	a = s[::-1]
	ans = 0
	(i, j) = (0, 0)
	while i < len(s):
		if s[i] == a[j]:
			j += 1
		else:
			ans += 1
		i += 1
	return ans
t = int(input())
while t > 0:
	s = input()
	print(calc(s))
	t -= 1


for i in range(int(input())):
	s = input()
	j = 0
	c = 0
	s2 = s[::-1]
	if s == s2:
		print(0)
	else:
		for i in range(0, len(s)):
			if s[i] == s2[j]:
				j += 1
			else:
				c += 1
		print(c)


for i in range(int(input())):
	S = input()
	a = 0
	r = 0
	d = S[::-1]
	s = -1
	if S == d:
		print(0)
	else:
		for k in range(len(S)):
			if d[r] == S[k]:
				r += 1
			else:
				a += 1
		print(a)


for i in range(int(input())):
	str1 = list(input())
	str2 = str1[::-1]
	x = 0
	j = 0
	for k in range(0, len(str1)):
		if str1[k] == str2[j]:
			j += 1
		else:
			x += 1
		k += 1
	print(x)


import sys
from math import sqrt, gcd
from collections import deque, Counter, OrderedDict
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	s = S()
	(c, n) = (0, len(s))
	j = n - 1
	for i in range(n):
		if s[i] == s[j]:
			c += 1
			j -= 1
	print(n - c)


t = int(input())
for i in range(t):
	s = input()
	r = s[::-1]
	a = 0
	j = 0
	for i in range(len(s)):
		if s[i] != r[j]:
			a += 1
		else:
			j += 1
	print(a)


import math
t = int(input())
for tc in range(t):
	str = input()
	n = len(str)
	rev = str[::-1]
	ans = 0
	j = 0
	i = 0
	while i < n:
		if str[i] == rev[j]:
			j += 1
		else:
			ans += 1
		i += 1
	print(ans)


t = int(input())
for k in range(t):
	s = input()
	r = s[::-1]
	(i, j, ct) = (0, 0, 0)
	while i < len(s):
		if s[i] == r[j]:
			i += 1
			j += 1
		else:
			i += 1
			ct += 1
	print(ct)


n = int(input())
for j in range(n):
	s = input()
	a = s[::-1]
	cnt = 0
	i = 0
	j = 0
	while i < len(s):
		if s[i] == a[j]:
			j += 1
		else:
			cnt += 1
		i += 1
	print(cnt)


for i in range(int(input())):
	s = input()
	rev_s = s[::-1]
	(i, j) = (0, 0)
	count = 0
	while i != len(s) and j != len(rev_s):
		if s[i] != rev_s[j]:
			count += 1
			i += 1
		else:
			i += 1
			j += 1
	print(count)


T = int(input())
for i in range(T):
	s = str(input())
	r = s
	r = r[::-1]
	(i, j, ans) = (0, 0, 0)
	while i < len(s):
		if s[i] == r[j]:
			j += 1
		else:
			ans += 1
		i += 1
	print(ans)


t = int(input())
for i in range(0, t):
	s = input()
	n = len(s)
	i = 0
	j = n - 1
	count = 0
	while i < n:
		if s[i] == s[j]:
			j -= 1
		else:
			count += 1
		i += 1
	print(count)


t = int(input())
for _ in range(t):
	a = list(input())
	n = len(a)
	print()
	if a == a[::-1]:
		print(0)
	else:
		j = 0
		for i in range(n):
			if a[i] == a[n - j - 1]:
				j += 1
		print(n - j)


import sys
input = sys.stdin.readline
T = int(input())

def testcase():
	a = input().split()[0]
	n = len(a)
	(i, j) = (0, n - 1)
	cnt = 0
	while i < n:
		if a[i] != a[j]:
			cnt += 1
		else:
			j -= 1
		i += 1
	print(cnt)
for _ in range(T):
	testcase()


T = int(input())
for _ in range(T):
	s = input()
	n = len(s)
	s_rev = s[::-1]
	j = n - 1
	r = 0
	for i in range(n - 1, -1, -1):
		if s_rev[i] == s[j]:
			j -= 1
		else:
			r += 1
	print(r)


for _ in range(int(input())):
	st = input()
	count = 0
	st1 = st[::-1]
	for i in range(len(st)):
		if st1[count] == st[i]:
			count += 1
	print(len(st) - count)


T = int(input())
for testCase in range(T):
	name = input()
	rev = name[::-1]
	(count, j) = (0, 0)
	for i in range(len(name)):
		if name[i] == rev[j]:
			j += 1
		else:
			count += 1
	print(count)


n = int(input())
for _ in range(n):
	arr = input()
	rev = arr[::-1]
	count = 0
	pos1 = len(arr) - 1
	pos2 = len(arr) - 1
	while pos2 >= 0:
		while pos2 >= 0 and rev[pos2] != arr[pos1]:
			pos2 -= 1
			count += 1
		if pos2 >= 0:
			pos2 -= 1
			pos1 -= 1
	print(count)


t = int(input())
for x in range(t):
	S = str(input())
	rev = S[::-1]
	count = 0
	j = 0
	for i in range(len(S)):
		if S[i] == rev[j]:
			j += 1
		else:
			count += 1
	print(count)


try:
	for _ in range(int(input())):
		a = input()
		b = a[::-1]
		count = 0
		i = 0
		j = 0
		while i < len(a) and j < len(b):
			if a[i] != b[j]:
				count += 1
				i = i + 1
			else:
				i = i + 1
				j = j + 1
		print(count)
except:
	pass


t = int(input())
for i in range(t):
	s = input()
	j = s[::-1]
	l = 0
	k = 0
	ans = 0
	for l in range(len(s)):
		if s[l] == j[k]:
			k = k + 1
		else:
			ans = ans + 1
			l = l + 1
	print(ans)


for i in range(int(input())):
	s = str(input())
	n = len(s)
	rev = s[::-1]
	count = 0
	j = 0
	for i in range(n):
		if s[i] == rev[j]:
			j += 1
		else:
			count += 1
	print(count)


from sys import stdin
input = stdin.readline
for _ in range(int(input().strip())):
	s = input().strip()
	n = len(s)
	k = s[::-1]
	(left, right) = (0, 0)
	cnt = 0
	while left < n:
		if s[left] != k[right]:
			cnt += 1
		else:
			right += 1
		left += 1
	print(cnt)


t = int(input())
for i in range(t):
	s = input()
	s1 = s[::-1]
	j = len(s) - 1
	c = 0
	for i in range(len(s) - 1, -1, -1):
		if s1[i] == s[j]:
			j -= 1
		else:
			c += 1
	print(c)


for i in range(int(input())):
	s = str(input())
	reverse = s[::-1]
	count = 0
	j = 0
	for i in range(len(s)):
		if s[i] == reverse[j]:
			j += 1
		else:
			count += 1
	print(count)


def check(s):
	return s[::-1]
for _ in range(int(input())):
	s = input()
	rev = check(s)
	a = 0
	b = rev[0]
	flag = 0
	for i in range(0, len(s)):
		if s[i] != b:
			flag += 1
		elif i != len(s) - 1:
			a += 1
			b = rev[a]
	print(flag)


t = int(input())
for i in range(t):
	s = input()
	s = list(s)
	r = s[::-1]
	(j, ans) = (0, 0)
	for i in range(len(s)):
		if s[i] == r[j]:
			j += 1
		else:
			ans += 1
	print(ans)


for _ in range(int(input())):
	x = input()
	y = x[::-1]
	i = 0
	j = 0
	ans = 0
	while i < len(x):
		if x[i] == y[j]:
			j += 1
		else:
			ans += 1
		i += 1
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	count = 0
	n = len(s)
	for i in range(n):
		if s[i] == s[n - count - 1]:
			count += 1
	print(n - count)


for j in range(int(input())):
	s = input()
	rev_s = s[::-1]
	c = 0
	for i in range(len(s)):
		if s[i] == rev_s[c]:
			c += 1
	print(len(s) - c)


for _ in range(int(input())):
	s = input()
	sr = s[::-1]
	j = 0
	for i in s:
		if i == sr[j]:
			j += 1
	print(len(s) - j)


for _ in range(int(input())):
	s = input()
	reversed_s = s[::-1]
	count = 0
	for i in range(len(s)):
		if s[i] == reversed_s[count]:
			count += 1
	print(len(s) - count)


for _ in range(int(input())):
	s = list(input())
	sr = s[:]
	sr.reverse()
	(i, j) = (0, 0)
	length = len(s)
	while i < length:
		if s[i] == sr[j]:
			j += 1
		i += 1
	print(length - j)


T = int(input())
for i in range(T):
	S = input()
	l = len(S)
	R = S[::-1]
	i = 0
	j = 0
	x = 0
	while i < l:
		if S[i] == R[j]:
			i += 1
			j += 1
		else:
			x += 1
			i += 1
	print(x)


def reverse(s):
	str = ''
	for i in s:
		str = i + str
	return str
t = int(input())
for i in range(0, t):
	s = input()
	r = reverse(s)
	i = 0
	j = 0
	ans = 0
	while i < len(s):
		if s[i] == r[j]:
			j = j + 1
		else:
			ans = ans + 1
		i = i + 1
	print(ans)


def maxLenPrefix(str1, str2):
	i = 0
	for j in range(len(str2)):
		if str1[i] == str2[j]:
			i += 1
		if i == len(str1):
			break
	return i

def main():
	t = int(input())
	for tx in range(t):
		pstr = input()
		fstr = pstr[::-1]
		maxPrefixLen = maxLenPrefix(fstr, pstr)
		print(len(fstr) - maxPrefixLen)
	return 0
main()


t = int(input())
for _ in range(t):
	s = input().rstrip()
	n = len(s)
	r = s[::-1]
	j = ans = 0
	for i in range(n):
		if s[i] == r[j]:
			j += 1
		else:
			ans += 1
	print(ans)


for _ in range(int(input())):
	s = input()
	r = s[::-1]
	(i, j) = (0, 0)
	result = 0
	while i < len(s):
		if s[i] == r[j]:
			j += 1
		else:
			result += 1
		i += 1
	print(result)


for t in range(int(input())):
	str = input()
	str2 = str[::-1]
	(i, j) = (0, 0)
	ans = 0
	while i != len(str):
		if str[i] == str2[j]:
			i += 1
			j += 1
		else:
			i += 1
			ans += 1
	print(ans)


T = int(input())
for test in range(T):
	S = input()
	N = len(S)
	count = 0
	for i in range(N):
		if S[i] == S[N - count - 1]:
			count += 1
	print(N - count)


try:
	for _ in range(int(input())):
		s = str(input())
		n = len(s)
		r = s[::-1]
		(count, j) = (0, 0)
		for i in range(n):
			if s[i] == r[j]:
				j += 1
			else:
				count += 1
		print(count)
except:
	pass


for _ in range(int(input())):
	s = input()
	a = []
	for i in s:
		a.append(i)
	n = len(s)
	r = a[::-1]
	j = 0
	ans = 0
	i = 0
	while i <= n - 1:
		if a[i] == r[j]:
			j += 1
			i += 1
		else:
			ans += 1
			i += 1
	print(ans)


for _ in range(int(input())):
	s = input()
	rev = s[::-1]
	c = 0
	j = 0
	for i in range(len(s)):
		if s[i] == rev[j]:
			j += 1
		else:
			c += 1
	print(c)