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 checker(a,b, arr):
    fr = [-1, -1]
    # print(a,b)
    for i in range(len(arr)):
        if arr[i]==a or arr[i]==b:
            if fr[0]==-1 and fr[1]==-1:
                if arr[i]==b:
                    a,b = b,a
                fr[0] = 1
                fr[1] = 0
            else:
                if arr[i]==a and fr[0]==fr[1]:
                    fr[0]+=1
                elif arr[i]==b and fr[1]==fr[0]-1:
                    fr[1]+=1
    # print(fr)
    an = max(min(fr)*2, ar[0][0])
    return an


test = int(input())
for _ in range(test):
    arr = list(input())
    if len(arr)==1 or len(arr)==2:
        print(0)
    else:
        freq = {}
        maxf = 0
        for i in range(len(arr)):
            freq[arr[i]] = freq.get(arr[i],0)+1
            maxf = max(maxf, freq[arr[i]])
        if len(freq)==len(arr):
            print(len(arr)-2)
        elif len(freq)==1:
            print(0)
        else:
            maxnn = 0
            ar = []
            for k,v in freq.items():
                ar.append((v,k))
            for i in range(10):
                for j in range(i+1,10):
                    nn = checker(str(i),str(j),arr)
                    maxnn = max(maxnn, nn)
            print(len(arr)-max(maxf, maxnn))