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 f(s,n):
    if n%2 != 0:
        return(False)
    else:
        p = s[0]
        q = s[1]
        for i in range(0,n,2):
            if s[i] != p:
                return(False)
        for i in range(1,n,2):
            if s[i] != q:
                return(False)
        return(True)
def g(s,i,j):
    k = 0
    while(int(s[k]) != i):
        k = k+1
    p = i
    q = j
    l = 1
    for m in range(k+1,n):
        if int(s[m]) == q:
            l = l+1
            q = p
            p = int(s[m])
    if l%2 == 0:
        return(l)
    else:
        return(l-1)
t = int(input())
while(t>0):
    t = t-1
    s = input()
    n = len(s)
    if f(s,n) == True:
        print(0)
    else:
        d = {}
        m = 0
        for i in s:
            j = int(i)
            if j in d:
                d[j] = d[j]+1
            else:
                d[j] = 1
            m = max(m,d[j])
        if m == 1:
            print(n-2)
        else:
            table = [[0 for i in range(10)]for j in range(10)]
            for i in range(10):
                if i not in d:
                    for j in range(10):
                        table[i][j] = 0
                else:
                    for j in range(10):
                        if j == i:
                            table[i][j] = d[i]
                        else:
                            if j not in d:
                                table[i][j] = 0
                            else:
                                table[i][j] = g(s,i,j)
            mi = 0
            for i in range(10):
                mi = max(mi,max(table[i]))
            print(n-mi)