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 collections import *
for _ in range(int(input())):
    a=input()
    s=list(a)
    # print(index)
    left=a[1:]+a[0]
    right=a[-1]+a[:len(a)-1]
    if(left==right):
        print(0)
    else:
        maxcount=0
        for i in range(0,10):
            count=0
            for j in range(0,len(a)):
                if(int(a[j])==i):
                    count+=1
            maxcount=max(count,maxcount)
        temp=0
        for i in range(0,10):
            for j in range(0,10):
                temp=0
                count=0
                for k in range(0,len(a)):
                    if(i!=j):
                        if(int(a[k])==i and temp==0):
                            temp=1
                            count+=1
                        if(int(a[k])==j and temp==1):
                            temp=0
                            count+=1
                if(count%2==1):
                    maxcount=max(count-1,maxcount)
                else:
                    maxcount=max(maxcount,count)
        print(len(a)-maxcount)
        # x=int(dic[0][0])
        # y=int(dic[1][0])
        # indexa=index[x]
        # indexb=index[y]
        # # print(indexa,indexb)
        # i=0
        # j=0
        # count1=0
        # while(i<len(indexa) and j<len(indexb)):
        #     # print(i,j)
        #     if(indexa[i]>indexb[j]):
        #         count1+=1
        #         while(indexa[i]>indexb[j]):

        #             j+=1
        #             if(j>=len(indexb)):
        #                 break
        #     else:
        #         count1+=1
        #         while(indexa[i]<indexb[j]):
        #             i+=1
        #             if(i>=len(indexa)):
        #                 break
        # # print(count1)
        # pairs=(count1+1)//2
        # # print(pairs)
        # print(min(len(a)-2,len(a)-dic[0][1],len(a)-2*pairs))