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.
# def help():
# 	n,q = map(int,input().split(" "))

# 	height = list(map(int,input().split(" ")))
# 	reward = list(map(int,input().split(" ")))

# 	if( n<= 1000 and q<= 1000):
# 		for qw in range(q):
# 			a,b,c = map(int,input().split(" "))
# 			b -= 1
# 			if( a == 1 ):
# 				height[b] = c
# 			# else:
# 			# 	if( height[b] > height[c] ):
				
					
# 			# 		for i in range(b,c+1,-1):



# 			# 	else:
# 	else:
# 		visited = [0]*n
# 		for i in range(n):
# 			if(height)

			
# for _ in range(1):
# 	help()
# from sys import stdin
# input = stdin.readline

# n = int(input())
# arr = list(map(int,input().split(" ")))

# dp = [[0]*n for i in range(n)]

# for i in range(1,n):
# 	arr[i] = arr[i]+arr[i-1]

# for l in range(2,n+1):
# 	for i in range(n-l+1):
# 		j = i+l-1
# 		if(i == 0 ):
# 			cnt = arr[j]
# 		else:
# 			cnt = arr[j] - arr[i-1]
# 		for k in range(i+1,j+1):
# 			dp[i][j] = max(dp[i][j] ,dp[i][k-1]+dp[k][j]+cnt)

# print dp[0][n-1]


# from random import randint

# n = 300
# points = []
# x = set()
# y = set()
# while len(x)!=n:
# 	x.add(randint(1,500))
# while len(y)!=n:
# 	y.add(randint(1,500))
# x = sorted(list(x))
# y = sorted(list(y))
# freq = [randint(1,10) for i in range(n)]
# mindist = 100000000000000
# minpts = []
# for i in range(500):
# 	# print(i)
# 	for j in range(500):
# 		cd = 0
# 		for k in range(n):
# 			cd += (abs(i-x[k])+ abs(j-y[k]))*freq[k]
		
# 		if(cd < mindist):
# 			mindist = cd
# 			minpts = [(i,j)]
# 		elif(cd == mindist):
# 			minpts.append((i,j))
# print(mindist)
# # print(minpts)

# valid = []
# for i in minpts:
# 	if(i[0] in x and i[1] in y):
# 		valid.append(i)
# print(valid)

# xrep = []
# yrep = []

# for i in range(n):
# 	for j in range(freq[i]):
# 		xrep.append(x[i])
# 		yrep.append(y[i])

# n1 = len(xrep)

# cd = 0
# for k in range(n):
# 	cd += (abs(xrep[n1//2]-x[k])+ abs(yrep[n1//2]-y[k]))*freq[k]

# print(cd)
# print((xrep[n1//2],yrep[n1//2]))



from sys import stdin
input = stdin.readline

def help():
	stri = list(input().strip())
	n = len(stri)
	if(n <= 2):
		print(0)
		return

	seti = list(set(stri))
	# print(seti)
	ans = 0
	for i in range(10):
		ans = max(ans,max(stri.count(str(i)),ans))

	for a in seti:
		for b in seti:
			if(a == b):
				continue
			cnt = 0
			for i in range(n):
				if(stri[i] == a and cnt%2 == 0):
					cnt += 1
				elif(stri[i] == b and cnt%2 == 1):
					cnt +=1
			# print(a,b,cnt)
			cnt = cnt - cnt%2
			ans = max(ans,cnt)
	print(n-ans)


for _ in range(int(input())):
	help()