Let's call left cyclic shift of some string t_1 t_2 t_3 ... t_{n - 1} t_n as string t_2 t_3 ... t_{n - 1} t_n t_1.

Analogically, let's call right cyclic shift of string t as string t_n t_1 t_2 t_3 ... t_{n - 1}.

Let's say string t is good if its left cyclic shift is equal to its right cyclic shift.

You are given string s which consists of digits 0–9.

What is the minimum number of characters you need to erase from s to make it good?

Input

The first line contains single integer t (1 ≤ t ≤ 1000) — the number of test cases.

Next t lines contains test cases — one per line. The first and only line of each test case contains string s (2 ≤ |s| ≤ 2 ⋅ 10^5). Each character s_i is digit 0–9.

It's guaranteed that the total length of strings doesn't exceed 2 ⋅ 10^5.

Output

For each test case, print the minimum number of characters you need to erase from s to make it good.

Example

Input


3
95831
100120013
252525252525


Output


3
5
0

Note

In the first test case, you can erase any 3 characters, for example, the 1-st, the 3-rd, and the 4-th. You'll get string 51 and it is good.

In the second test case, we can erase all characters except 0: the remaining string is 0000 and it's good.

In the third test case, the given string s is already good.
#input()
# dic = {4:5,2:2,1:8,3:4,5:1}
# dic = sorted(dic,key = dic.keys())
# print(dic)


# print((2|3|32|43|8)|(43), 2|32|8)
# print(2|3|32|43|8, 3|43, 32|8, 43, 8)

# class Node:
# 	def __init__ (self,x):
# 		self.val = x
# 		self.left  = None
# 		self.right = None

# def treeprint(root):
# 	if root:
# 		treeprint(root.left)
# 		print(root.val,end = " ")
# 		treeprint(root.right)

# arr = [1,2,3,4,5]
# root = Node(arr[len(arr)//2])
# def buildTree(root,left,right):
# 	if left:
# 		root.left = Node(left[len(left)//2])
# 		buildTree(root.left,left[:len(left)//2],left[len(left)//2 +1:])
# 	if right:
# 		root.right = Node(right[len(right)//2])
# 		buildTree(root.right,right[:len(right)//2],right[len(right)//2 +1:])

# buildTree(root,arr[:len(arr)//2],arr[len(arr)//2 +1:])


# treeprint(root)
# print()
for _ in range(int(input())):
	s = input()
	n = len(s)
	pairs = []
	for i in range(10):
		for j in range(10):
			pairs.append(str(i)+str(j))
	maxx = 0
	for i in pairs:
		c = 0
		v = i[0]
		for j in range(n):
			if s[j]==v:
				c+=1
				if v==i[0]:
					v = i[1]
				else:
					v = i[0]
		if v==i[1] and i[0]!=i[1]:
			c-=1
		maxx = max(c,maxx)
	print(n-maxx)




