Megan is playing a string game with the following rules:

It starts with a string, $\boldsymbol{\mathrm{~S~}}$.

During each turn, she performs the following move:

Choose an index in $\boldsymbol{\mathrm{~S~}}$. The chosen index must be strictly greater than any index chosen in a prior move. 
Perform one or more circular rotations (in either direction) of the suffix starting at the chosen index.

For example, let's say $\boldsymbol{s}=$ abcdefjghi. During our move, we choose to do three right rotations of the suffix starting at index $\boldsymbol{6}$: 

Note that this counts as one move.

The goal of the game is to convert $\boldsymbol{\mathrm{~S~}}$ into the lexicographically smallest possible string in as few moves as possible. In other words, we want the characters to be in alphabetical order.

Megan plays this game $\mathrm{~g~}$ times, starting with a new string $\boldsymbol{\mathrm{~S~}}$ each time. For each game, find the minimum number of moves necessary to convert $\boldsymbol{\mathrm{~S~}}$ into the lexicographically smallest string and print that number on a new line.

Input Format

The first line contains an integer, $\mathrm{~g~}$, denoting the number of games. 

Each of the $\mathrm{~g~}$ subsequent lines contains a single string denoting the initial value of string $\boldsymbol{\mathrm{~S~}}$ for a game.

Constraints

$1\leq g\leq100$
$1\leq|s|\leq1000$
$\boldsymbol{\mathrm{~S~}}$ consists of lowercase English alphabetic letters only.

Output Format

For each game, print an integer on a new line denoting the minimum number of moves required to convert $\boldsymbol{\mathrm{~S~}}$ into the lexicographically smallest string possible.

Sample Input 0
3
abcdefghij
acab
baba

Sample Output 0
0
1
2

Explanation 0

We play the following $g=3$ games:

In the first game, abcdefghij is already as lexicographically small as possible (each sequential letter is in alphabetical order). Because we don't need to perform any moves, we print $\mbox{0}$ on a new line.
In the second game, we rotate the suffix starting at index $\mbox{1}$, so acab becomes aabc.
Because the string is lexicographically smallest after one move, we print $\mbox{1}$ on a new line.

In the third game, we perform the following moves:

Rotate the suffix starting at index $\mbox{0}$ (i.e., the entire string), so baba becomes abab. 
Rotate the suffix starting at index $\mbox{1}$, so abab becomes aabb.

Because the string is lexicographically smallest after two moves, we print $2$ on a new line.

Source: hackerrank | Difficulty: HARD
Tags: Dynamic programming


Solutions:
def tek(lista, tal=None):
	if tal != None:
		lista2 = lista[tal:] + lista[:tal]
		print(''.join([chr(ord('a') + i) for i in lista]), ''.join([chr(ord('a') + i) for i in lista2]))
		print(' ' * tal + '^')
	else:
		print(*[chr(ord('a') + i) for i in lista], sep='')

def brute(S):
	if len(S) == 0:
		return 0
	c_min = -1
	while min(S) != c_min:
		c_min = min(S)
		while S[0] == c_min:
			S = S[1:]
			if len(S) == 0:
				return 0
	mini = 78678687687
	for (ind, num) in enumerate(S):
		if num == c_min:
			mini = min(mini, brute(S[ind + 1:] + S[:ind]))
	return mini + 1

def secondVal(S):
	x = S[0]
	ind = 0
	while S[ind] == x:
		ind += 1
		if ind >= len(S):
			return ind
	return ind
cost = {}

def concept(S):
	if len(S) == 0:
		return 0
	prev = 0
	Snew = []
	for c in S:
		if c != prev:
			prev = c
			Snew.append(c)
	S = tuple(Snew)
	if S not in cost:
		cs = min(S)
		while S[0] == cs:
			cut_index = secondVal(S)
			S = S[cut_index:]
			if len(S) == 0:
				return 0
			cs = min(S)
		ind_c = []
		cutted_S = []
		cutted_id = 0
		for (ind, test_c) in enumerate(S):
			if test_c == cs:
				ind_c.append(cutted_id)
			else:
				cutted_S.append(test_c)
				cutted_id += 1
		cutted_S = tuple(cutted_S)
		mini = 2984924
		for ind in ind_c:
			mini = min(mini, concept(cutted_S[ind:] + cutted_S[:ind]) + len(ind_c))
		cost[S] = mini
	return cost[S]

def closeconcept(S, cs):
	possi = [False] * len(S)
	cost = [10000] * len(S)
	possi[0] = True
	for c in sorted(list(set(S))):
		ind_c = []
		for (ind, test_c) in enumerate(S):
			if test_c == c:
				ind_c.append(ind)
		new_possi = [False] * len(S)
		newcost = [100000] * len(S)
		for i in range(len(S)):
			if possi[i]:
				for ind in ind_c:
					newind = (i + ind) % len(S)
					newpossi[newind] = True
					if ind == 0:
						newcost[newind] = min(newcost[newind], cost[i])
					else:
						newcost[newind] = min(newcost[newind], cost[i] + 1)

def onefirst(d, ind1, ind2):
	start1 = ind1
	start2 = ind2
	n = len(d)
	while d[ind1] == d[ind2]:
		prevd1 = d[ind1]
		prevd2 = d[ind2]
		ind1 = (ind1 + 1) % n
		ind2 = (ind2 + 1) % n
		if ind1 == start1:
			return True
		if prevd1 > d[ind1]:
			return True
		if prevd2 > d[ind2]:
			return False
	if d[ind1] < d[ind2]:
		return False
	else:
		return True
q = int(input())
for _ in range(q):
	data = [ord(x) - ord('a') for x in input()]
	prev = -1
	d = []
	for c in data:
		if c != prev:
			prev = c
			d.append(c)
	d = tuple(d)
	if len(d) == 0 or d == sorted(d):
		print(0)
		continue
	Sc = sorted(tuple(set(d)))
	S = [()] * len(Sc)
	markers = [[] for x in range(len(Sc) - 1)]
	mapps = [()] * (len(Sc) - 1)
	firsttimers = [set() for x in range(len(Sc) - 1)]
	S[0] = d
	for (ind, c) in enumerate(Sc[:-1]):
		cutS = []
		cutIndex = 0
		cutIndecies = []
		mapp = []
		for (a_ind, a) in enumerate(S[ind]):
			if a != c:
				cutS.append(a)
				mapp.append(cutIndex)
				cutIndex += 1
			else:
				mapp.append(cutIndex)
				cutIndecies.append(a_ind)
		firsttime = set()
		if len(cutIndecies) > 0:
			circular = [cutIndecies[-1]] + cutIndecies
			for (cutsind, cuts) in enumerate(cutIndecies):
				if (cuts - circular[cutsind]) % len(S[ind]) != 1:
					firsttime.add(cuts)
		S[ind + 1] = tuple(cutS)
		mapps[ind] = tuple(mapp)
		markers[ind] = tuple(cutIndecies)
		firsttimers[ind] = firsttime
	d_superconcept = [{} for _ in range(len(Sc))]

	def superconcept(rot, k, n):
		if k == 0:
			return 0
		if rot not in d_superconcept[k]:
			newrots = [mapps[n - k - 1][cut] for cut in markers[n - k - 1]]
			oldrot = mapps[n - k - 1][rot]
			mini = 743874387
			for (ind, newrot) in enumerate(newrots):
				if len(firsttimers[n - k - 1]) == 1 and rot == markers[n - k - 1][ind] and (rot in firsttimers[n - k - 1]):
					cost = len(firsttimers[n - k - 1]) - 1
				elif rot != markers[n - k - 1][ind] and rot in firsttimers[n - k - 1] and (markers[n - k - 1][ind] in firsttimers[n - k - 1]):
					cost = len(firsttimers[n - k - 1]) - 1
				else:
					cost = len(firsttimers[n - k - 1])
				mini = min(mini, superconcept(newrot % len(S[n - k]), k - 1, n) + cost)
			d_superconcept[k][rot] = mini
		return d_superconcept[k][rot]
	superOUT = superconcept(0, len(Sc) - 1, len(Sc))
	print(superOUT)


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


def tek(lista, tal=None):
	if tal != None:
		lista2 = lista[tal:] + lista[:tal]
		print(''.join([chr(ord('a') + i) for i in lista]), ''.join([chr(ord('a') + i) for i in lista2]))
		print(' ' * tal + '^')
	else:
		print(*[chr(ord('a') + i) for i in lista], sep='')

def brute(S):
	if len(S) == 0:
		return 0
	c_min = -1
	while min(S) != c_min:
		c_min = min(S)
		while S[0] == c_min:
			S = S[1:]
			if len(S) == 0:
				return 0
	mini = 78678687687
	for (ind, num) in enumerate(S):
		if num == c_min:
			mini = min(mini, brute(S[ind + 1:] + S[:ind]))
	return mini + 1

def secondVal(S):
	x = S[0]
	ind = 0
	while S[ind] == x:
		ind += 1
		if ind >= len(S):
			return ind
	return ind
cost = {}

def concept(S):
	if len(S) == 0:
		return 0
	prev = 0
	Snew = []
	for c in S:
		if c != prev:
			prev = c
			Snew.append(c)
	S = tuple(Snew)
	if S not in cost:
		cs = min(S)
		while S[0] == cs:
			cut_index = secondVal(S)
			S = S[cut_index:]
			if len(S) == 0:
				return 0
			cs = min(S)
		ind_c = []
		cutted_S = []
		cutted_id = 0
		for (ind, test_c) in enumerate(S):
			if test_c == cs:
				ind_c.append(cutted_id)
			else:
				cutted_S.append(test_c)
				cutted_id += 1
		cutted_S = tuple(cutted_S)
		mini = 2984924
		for ind in ind_c:
			mini = min(mini, concept(cutted_S[ind:] + cutted_S[:ind]) + len(ind_c))
		cost[S] = mini
	return cost[S]

def closeconcept(S, cs):
	possi = [False] * len(S)
	cost = [10000] * len(S)
	possi[0] = True
	for c in sorted(list(set(S))):
		ind_c = []
		for (ind, test_c) in enumerate(S):
			if test_c == c:
				ind_c.append(ind)
		new_possi = [False] * len(S)
		newcost = [100000] * len(S)
		for i in range(len(S)):
			if possi[i]:
				for ind in ind_c:
					newind = (i + ind) % len(S)
					newpossi[newind] = True
					if ind == 0:
						newcost[newind] = min(newcost[newind], cost[i])
					else:
						newcost[newind] = min(newcost[newind], cost[i] + 1)

def onefirst(d, ind1, ind2):
	start1 = ind1
	start2 = ind2
	n = len(d)
	while d[ind1] == d[ind2]:
		prevd1 = d[ind1]
		prevd2 = d[ind2]
		ind1 = (ind1 + 1) % n
		ind2 = (ind2 + 1) % n
		if ind1 == start1:
			return True
		if prevd1 > d[ind1]:
			return True
		if prevd2 > d[ind2]:
			return False
	if d[ind1] < d[ind2]:
		return False
	else:
		return True
q = int(input())
for _ in range(q):
	data = [ord(x) - ord('a') for x in input()]
	prev = -1
	d = []
	for c in data:
		if c != prev:
			prev = c
			d.append(c)
	d = tuple(d)
	if len(d) == 0 or d == sorted(d):
		print(0)
		continue
	Sc = sorted(tuple(set(d)))
	S = [()] * len(Sc)
	markers = [[] for x in range(len(Sc) - 1)]
	mapps = [()] * (len(Sc) - 1)
	firsttimers = [set() for x in range(len(Sc) - 1)]
	S[0] = d
	for (ind, c) in enumerate(Sc[:-1]):
		cutS = []
		cutIndex = 0
		cutIndecies = []
		mapp = []
		for (a_ind, a) in enumerate(S[ind]):
			if a != c:
				cutS.append(a)
				mapp.append(cutIndex)
				cutIndex += 1
			else:
				mapp.append(cutIndex)
				cutIndecies.append(a_ind)
		firsttime = set()
		if len(cutIndecies) > 0:
			circular = [cutIndecies[-1]] + cutIndecies
			for (cutsind, cuts) in enumerate(cutIndecies):
				if (cuts - circular[cutsind]) % len(S[ind]) != 1:
					firsttime.add(cuts)
		S[ind + 1] = tuple(cutS)
		mapps[ind] = tuple(mapp)
		markers[ind] = tuple(cutIndecies)
		firsttimers[ind] = firsttime
	d_superconcept = [{} for _ in range(len(Sc))]

	def superconcept(rot, k, n):
		if k == 0:
			return 0
		if rot not in d_superconcept[k]:
			newrots = [mapps[n - k - 1][cut] for cut in markers[n - k - 1]]
			oldrot = mapps[n - k - 1][rot]
			mini = 743874387
			for (ind, newrot) in enumerate(newrots):
				if len(firsttimers[n - k - 1]) == 1 and rot == markers[n - k - 1][ind] and (rot in firsttimers[n - k - 1]):
					cost = len(firsttimers[n - k - 1]) - 1
				elif rot != markers[n - k - 1][ind] and rot in firsttimers[n - k - 1] and (markers[n - k - 1][ind] in firsttimers[n - k - 1]):
					cost = len(firsttimers[n - k - 1]) - 1
				else:
					cost = len(firsttimers[n - k - 1])
				mini = min(mini, superconcept(newrot % len(S[n - k]), k - 1, n) + cost)
			d_superconcept[k][rot] = mini
		return d_superconcept[k][rot]
	superOUT = superconcept(0, len(Sc) - 1, len(Sc))
	print(superOUT)


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import math
import os
import random
import re
import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for q_itr in range(q):
	s = input()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))


import sys

def bestlastrotation(s, groups, letters, memos):
	if len(letters) < 3:
		return groups[0]
	mn = letters[0]
	mn2 = letters[1]
	mn3 = letters[2]
	lens = len(s)
	groups2 = []
	for g in groups:
		i = g
		while s[i] == mn:
			i = (i + 1) % lens
		if s[i] == mn2 and s[g - 1] != mn2:
			groups2.append([g, i])
	if len(groups2) == 0:
		return groups[0]
	if len(groups2) == 1:
		return groups2[0][0]
	for gg in groups2:
		j = gg[1]
		while s[j] == mn2 or s[j] == mn:
			j = (j + 1) % lens
		if s[j] != mn3:
			return gg[0]
		else:
			gg.append(j)
	if len(letters) < 4:
		return groups2[0][0]
	groupset = set((x[0] for x in groups2))
	ans = 0
	best = lens
	for g in groupset:
		s2 = (s[g:] + s[:g]).replace(mn, '')
		result = min_rotations(s2, memos)
		if best > result:
			best = result
			ans = g
	return ans

def min_rotations(s, memos):
	if s in memos:
		return memos[s]
	letters = sorted(set(s))
	mn = min(letters)
	ans = 0
	while mn != max(letters):
		i = 0
		while s[i] == mn:
			i += 1
		if i > 0:
			s = s[i:]
		groups = []
		for i in range(len(s)):
			if s[i] == mn and s[i - 1] != mn:
				groups.append(i)
		ans += len(groups)
		if len(groups) == 1:
			g = groups[0]
			s = s[g:] + s[:g]
		if len(groups) > 1:
			g = bestlastrotation(s, groups, letters, memos)
			s = s[g:] + s[:g]
		s = s.replace(mn, '')
		letters = letters[1:]
		mn = min(letters)
	memos[s] = ans
	return ans
q = int(input().strip())
for a0 in range(q):
	s = input().strip()
	print(min_rotations(s, dict()))