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 math import sqrt
for _ in range (int(input())):
    s = input()
    index = [[] for i in range (10)]
    present = [[0 for j in range (len(s))] for i in range (10)]
    for i in range (len(s)):
        if i!=0:
            for j in range (10):
                present[j][i]+=present[j][i-1]
        present[int(s[i])][i]+=1
    maxx = 0
    for i in present:
        maxx = max(maxx,i[-1])

    for i in range (len(s)):
        index[int(s[i])].append(i)
    final = 0
    ind1 = 0
    ind2 = 0
    for i in range (len(index)):
        other = [0]*10
        for j in range (1,len(index[i])):
            one = index[i][j-1]
            two = index[i][j]
            for k in range (10):
                if present[k][two]-present[k][one]!=0 and k!=i:
                    other[k]+=1
        for j in range (10):
            if len(index[i])!=0 and j!=i and present[j][-1] - present[j][index[i][-1]]>=1:
                other[j]+=1
            elif j!=i and len(index[i])!=0 and present[j][index[i][0]] - present[j][0]>=1:
                other[j]+=1
            elif len(index[i])!=0 and index[i][0]!=0 and present[j][0]==1:
                other[j] += 1


        total = max(other)
        if total > final:
            final = total
    ava = (2*final)
    if maxx > ava:
        ava = maxx
    
    print(len(s)-ava)