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.*;
import java.util.*;


public class Main {
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private static final boolean OFFLINE_WITHOUT_FILES = false;


    void solve() throws  IOException{
        int t=readInt();
        char [] allNum=new char[10];
        allNum[0]='0';
        for (int i=1;i<10;++i){
            allNum[i]=(char)(allNum[i-1]+1);
        }
        while (--t>=0) {
            String inpStr = readString();
            int answer=0;
            for (int i=0;i<10;++i){
                for (int j=i;j<10;++j){
                    int current=0;
                    boolean [] goodIndexes=new boolean[inpStr.length()];
                    int count=0;
                    int firstIndex=inpStr.length();
                    for (int indexStr=0;indexStr<inpStr.length();++indexStr){
                        goodIndexes[indexStr]=false;
                        if (inpStr.charAt(indexStr)==allNum[i]||inpStr.charAt(indexStr)==allNum[j]){
                            ++count;
                            firstIndex=Math.min(firstIndex,indexStr);
                            goodIndexes[indexStr]=true;
                        }
                    }
                    if (i==j||count==0){
                        answer=Math.max(answer,count);
                    }
                    else {
                        current=1;
                        char lastChar=inpStr.charAt(firstIndex);
                        for (int indexStr=firstIndex;indexStr<inpStr.length();++indexStr){
                            if ((inpStr.charAt(indexStr)!=lastChar)&&(goodIndexes[indexStr])){
                                lastChar=inpStr.charAt(indexStr);
                                ++current;
                            }
                        }
                        answer=Math.max(answer,current-current%2);
                    }

                }
            }
            out.println(inpStr.length()-answer);
        }
    }

    public static void main(String[] args) {
        new Main();
    }

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok;

    Main() {
        try {
            long timeStart = System.currentTimeMillis();
            if (ONLINE_JUDGE || OFFLINE_WITHOUT_FILES) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }

            tok = new StringTokenizer("");
            solve();
            out.close();
            long timeEnd = System.currentTimeMillis();
            System.err.println("time = " + (timeEnd - timeStart) + " compiled");
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }
    }

    String readLine() throws IOException {
        return in.readLine();
    }

    String delimiter = " ";

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (nextLine == null)
                return null;
            tok = new StringTokenizer(nextLine);
        }
        return tok.nextToken(delimiter);
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    int[] sortArrayInt(int[] a) {
        Integer[] arr = new Integer[a.length];
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
        Arrays.sort(arr);
        for (int i = 0; i < a.length; i++) {
            a[i] = arr[i];
        }
        return a;
    }

    void sortArrayLong(long[] a) {
        Long[] arr = new Long[a.length];
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
        Arrays.sort(arr);
        for (int i = 0; i < a.length; i++) {
            a[i] = arr[i];
        }
    }
}