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 java.util.*;
import java.io.*;
public class Main implements Runnable{
    FastScanner sc;
    PrintWriter pw;
    final class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            try {
                br = new BufferedReader(new InputStreamReader(System.in));
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
 
        public long nlo() {
            return Long.parseLong(next());
        }
 
        public String next() {
            if (st.hasMoreTokens()) return st.nextToken();
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
            return st.nextToken();
        }
 
        public int ni() {
            return Integer.parseInt(next());
        }
 
        public String nli() {
            String line = "";
            if (st.hasMoreTokens()) line = st.nextToken();
            else try {
                return br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            while (st.hasMoreTokens()) line += " " + st.nextToken();
            return line;
        }
 
        public double nd() {
            return Double.parseDouble(next());
        }
    }
    public static void main(String[] args) throws Exception
    {
        new Thread(null,new Main(),"codeforces",1<<28).start();
    }
    public void run()
    {
        sc=new FastScanner();
        pw=new PrintWriter(System.out);
        solve();
        pw.flush();
        pw.close();
    }
    public long gcd(long a,long b)
    {
        return b==0L?a:gcd(b,a%b);
    }
    public long ppow(long a,long b,long mod)
    {
        if(b==0L)
        return 1L;
        long tmp=1;
        while(b>1L)
        {
            if((b&1L)==1)
            tmp*=a;
            a*=a;
            a%=mod;
            tmp%=mod;
            b>>=1;
        }
        return (tmp*a)%mod;
    }
    public  int gcd(int x,int y)
    {
        return y==0?x:gcd(y,x%y);
    }
    public class Pair implements Comparable<Pair>{
        int x;
        int val;
        Pair(int a,int b)
        {
            x=a;
            val=b;
        }
        public int compareTo(Pair b)
        {
            return this.val-b.val;
        }
        public Pair clone(Pair b)
        {
            return new Pair(b.x,b.val);
        }
    }
    //////////////////////////////////
    /////////////  LOGIC  ///////////
    ////////////////////////////////
    public void solve(){
        int t=sc.ni();
        while(t-->0)
        {
         char[] arr=sc.next().toCharArray();
         int[] frr,frr1;
         frr=new int[10];
         frr1=new int[10];
         for(int i=0;i<arr.length;i++)
           frr[arr[i]-'0']++;
        int ans=0;
        for(int i=0;i<=9;i++)
            ans=Math.max(ans,frr[i]);
        ans=arr.length-ans;
        for(int i=0;i<=9;i++)
        {
           for(int j=0;j<=9;j++)
           {
               if(i==j)
               continue;
               else
               {
                   int pp=0,l=0;
                   for(int k=0;k<arr.length;k++)
                   {
                       if((pp==0)&&((int)(arr[k]-'0')==i))
                       {
                           l++;
                           pp^=1;
                       }
                       else if(((pp==1)&&((int)(arr[k]-'0')==j)))
                       {
                            l++;
                            pp^=1;
                       }
                   }
                   if(l%2==1)
                   l--;
                   ans=Math.min(ans,arr.length-l);
                   //pw.println(ans+" "+i +" "+j);
               }
           } 
        }
        pw.println(ans);
    }
}
}