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.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.PrintWriter;
import java.util.ArrayList;

public class C {

	static String s; 
	
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
	    PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	    
	    int t = sc.nextInt();
	    while(t-- > 0) {
	    	s = sc.nextLine();
	    	int[] digit_count = new int[10];
	    	for(int i = 0; i < s.length(); i++) {
	    		digit_count[Character.getNumericValue(s.charAt(i))]++;
	    	}
	    	
	    	long ans = 2;
	    	for(int digit : digit_count)
	    		ans = Math.max(ans, digit);
	    	
	    	// find best ans of all 2 digit permutations
	    	for(int i = 0; i <= 9; i++) {
	    		for(int j = 0; j <= 9; j++) {	
	    			if(i == j) continue;
	    			
	    			int curr = 0;
	    			int ptr = 0;
	    			boolean found = true;
	    			while(found) {
	    				int index1 = firstFrom(i, ptr);
	    				if(index1 == -1) {
	    					found = false;
	    					continue;
	    				}
	    				ptr = index1 + 1;
	    				
	    				int index2 = firstFrom(j, ptr);
	    				if(index2 == -1) {
	    					found = false;
	    					continue;
	    				}
	    				ptr = index2 + 1;
	    				
	    				curr++;
	    			}
	    			
	    			ans = Math.max(ans, curr*2);
	    				
	    		}
	    	}
	    	
	    	out.println(s.length() - ans);
	    }
	    
	    out.close();
	}
	
	public static int firstFrom(int key, int index) {
		int i;
		boolean found = false;
		for(i = index; i < s.length(); i++) {
			if(getInt(s.charAt(i)) == key) {
				found = true;
				break;
			}
		}
		
		if(found)
			return i;
		else
			return -1;
	}
	
	public static int getInt(char c) {
		return Character.getNumericValue(c);
	}
	
	private static class FastScanner {
        private int BS = 1<<16;
        private char NC = (char)0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;
 
        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }
 
        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            }
            catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }
 
        private char getChar(){
            while(bId==size) {
                try {
                    size = in.read(buf);
                }catch(Exception e) {
                    return NC;
                }
                if(size==-1)return NC;
                bId=0;
            }
            return (char)buf[bId++];
        }
 
        public int nextInt() {
            return (int)nextLong();
        }
 
        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }
 
        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }
 
        public long nextLong() {
            cnt=1;
            boolean neg = false;
            if(c==NC)c=getChar();
            for(;(c<'0' || c>'9'); c = getChar()) {
                if(c=='-')neg=true;
            }
            long res = 0;
            for(; c>='0' && c <='9'; c=getChar()) {
                res = (res<<3)+(res<<1)+c-'0';
                cnt*=10;
            }
            return neg?-res:res;
        }
 
        public double nextDouble() {
            double cur = nextLong();
            return c!='.' ? cur:cur+nextLong()/cnt;
        }
 
        public String next() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c>32) {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }
 
        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c!='\n' && c != '\r') {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }
 
        public boolean hasNext() {
            if(c>32)return true;
            while(true) {
                c=getChar();
                if(c==NC)return false;
                else if(c>32)return true;
            }
        }
    }
}
