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.
import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
input=sys.stdin.readline
##import numpy as np
#sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
def msb(n):         #lowest two ki power
    n|=n>>1
    n|=n>>2
    n|=n>>4
    n|=n>>8
    n|=n>>16
    n|=n>>32
    n|=n>>64
    return n-(n>>1)
def pref(a,n,f):             
    pre=[0]*n
    if(f==0):         ##from beginning
        pre[0]=a[0]
        for i in range(1,n):
            pre[i]=a[i]+pre[i-1]
    else:              ##from end
        pre[-1]=a[-1]
        for i in range(n-2,-1,-1):
            pre[i]=pre[i+1]+a[i]
    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far

##seq=np.array([0,1,2,2,3,3,4,4,4,5],dtype=int)
##seq1=np.array([0,1,5,9,18,27,43,59,75,100],dtype=int)
##
##for i in range(10,1000000000):
##    seq=np.append(seq,(1+seq[i-seq[seq[i-1]]])%mo)
##    seq1=np.append(seq1,(seq1[-1]+seq[-1]*seq[-1])%mo)
##for i in range(inin()):
##    l,r=cin()
##    print(seq1[r]-seq1[l-1])
##for _ in range(inin()):
##    n,k,z=cin()
##    l=ain()
##    pre=pref(l,n,0);f=0
##    if(z==0 or k==1 ):
##        ans=pre[k]
##        de=l[:k]
##    else:
##        ans=l[0]+l[1]
##        de=[l[0],l[1]]
##        k-=1
##        i=1
##        while(k!=0):
##            print((l[i-1]+l[i]+pre[i+k-2]-pre[i]),(pre[i+k]-pre[i]))
##            if((z>0 and (l[i-1]+l[i]+pre[i+k-2]-pre[i])>(pre[i+k]-pre[i]) and f==0) or (i==n-1)):
##                f=1
##                ans+=l[i-1]
##                de+=[l[i-1]]
##                z-=1
##                i-=1
##            else:
##                f=0
##                ans+=l[i+1]
##                de+=[l[i+1]]
##                i+=1
##            k-=1
##    print(ans)
##    print(de)
for _ in range(inin()):
    s=sin().strip()
    d=dd(list);d1=dd(int)
    n=len(s)
    for i in range(n):
        d[s[i]]+=[i]
        d1[s[i]]+=1
    ans=max(d1.values())
    l=list(d.keys())
##    print(l)
    for i in l:
        for j in l:
            if(i!=j):
                l1=d[i]+d[j]
                l1.sort()
##                print(l1)
                curr=i
                te=1
                p=l1.index(d[i][0])
                for k in l1[p+1:]:
                    if(s[k]==curr):continue
                    else:
                        te+=1
                        if(curr==i):curr=j
                        else:curr=i
                if(te%2==1):te-=1
##                print(i,j,te)
                ans=max(ans,te)
                l1=[]
    print(n-ans)
                    
                    
                
            
            
                
            
    
    
    

            
    
        
        
                
    
    
    
    
    
