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 Solution{
    
    public static int solve(String s){
        
        int ans=2;
        
        // odd check
        int[] arr=new int[10];
        
        for(int f=0;f<s.length();f++){
            arr[s.charAt(f)-'0']++;        
        }
        
        for(int w=0;w<10;w++){
            ans=Math.max(ans,arr[w]);
        }
        
        // even check
        for(int d1=0;d1<=10;d1++){
            for(int d2=0;d2<=10;d2++){
                
                boolean flag=true;
                int ctr=0;
                
                for(int x=0;x<s.length();x++){
                    if(flag){
                        if(s.charAt(x)-'0'==d1){
                            flag=false;
                            ctr++;
                        }
                    }
                    else{
                        if(s.charAt(x)-'0'==d2){
                            flag=true;
                            ctr++;
                        }
                    }
                }
                
                if(d1==d2){
                    ans=Math.max(ans,ctr);
                }
                else{
                    if(ctr%2==0){
                        ans=Math.max(ans,ctr);
                    }
                }
                                
            }
        }
        
        return ans;
        
    }
    
    public static void main(String[] args) throws IOException{
        Re.init(System.in);
        PrintWriter pw=new PrintWriter(System.out);
        
        int t=Re.nextInt();
        
        for(int i=0;i<t;i++){
            String s=Re.next();
            pw.println(s.length()-solve(s));
        }
        
        pw.close();
    }
}

/** Class for buffered reading int and double values */
class Re {
	static BufferedReader reader;
	static StringTokenizer tokenizer;

	/** call this method to initialize reader for InputStream */
	static void init(InputStream input) {
		reader = new BufferedReader(new InputStreamReader(input));
		tokenizer = new StringTokenizer("");
	}

	/** get next word */
	static String next() throws IOException {
		while (!tokenizer.hasMoreTokens()) {
			// TODO add check for eof if necessary
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}

	static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	static double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
	
	static long nextLong() throws IOException {
		return Long.parseLong(next());
	}
}