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.
from os import path;import sys,time
mod = int(1e9 + 7)
from math import ceil, floor,gcd,log,log2 ,factorial,sqrt
from collections import defaultdict ,Counter , OrderedDict , deque;from itertools import combinations,permutations
# from string import ascii_lowercase ,ascii_uppercase
from bisect import *;from functools import reduce;from operator import mul;maxx = float('inf')
I = lambda :int(sys.stdin.buffer.readline())
lint = lambda :[int(x) for x in sys.stdin.buffer.readline().split()]
S = lambda: sys.stdin.readline().strip('\n')
grid = lambda  r :[lint() for i in range(r)]
localsys = 0
start_time = time.time()
#left shift --- num*(2**k) --(k - shift)
nCr = lambda n, r: reduce(mul, range(n - r + 1, n + 1), 1) // factorial(r)
def ceill(n,x):
    return (n+x -1 )//x
T =1
def solve():
	s = S()
	n ,cnt  = len(s) , [0]*10
	for i in s:
		cnt[int(i)]+=1
	st , ans = set(s) , n - max(cnt)
	# print(ans,"pp",cnt)
	for i in st:
		for j in st:
			if i ==j:
				continue
			sr = ''.join([kl for kl in s if kl ==i or kl == j])
			ans = min(ans , n - 2*sr.count(i+j) )
	print(ans)



	


		







def run():
    if (path.exists('input.txt')):
        sys.stdin=open('input.txt','r')
        sys.stdout=open('output.txt','w')


run()
T = I() if T else 1
for _ in range(T):
    solve()


if localsys:
    print("\n\nTime Elased :",time.time() - start_time,"seconds")


