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

public class Main
{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tokenizer=null;

    public static void main(String[] args) throws IOException
    {
        new Main().execute();
    }

    void debug(Object...os)
    {
        System.out.println(Arrays.deepToString(os));
    }

    int ni() throws IOException
    {
        return Integer.parseInt(ns());
    }

    long nl() throws IOException
    {
        return Long.parseLong(ns());
    }

    double nd() throws IOException
    {
        return Double.parseDouble(ns());
    }

    String ns() throws IOException
    {
        while (tokenizer == null || !tokenizer.hasMoreTokens())
            tokenizer = new StringTokenizer(br.readLine());
        return tokenizer.nextToken();
    }

    String nline() throws IOException
    {
        tokenizer=null;
        return br.readLine();
    }


    //Main Code starts Here
    int totalCases, testnum;
    int k;
    int z;

    void execute() throws IOException
    {
        totalCases = ni();
        for(testnum = 1; testnum <= totalCases; testnum++)
        {
            if(!input())
                break;
            solve();
        }
    }

    void solve() throws IOException
    {
        String str = ns();

        if( str.length() <=2 ) {
            System.out.println("0");
            return;
        }



        int max = 2;
        for( char i='0'; i<='9'; i++) {
            for( char j='0'; j<='9'; j++) {
                char current = i;
                int len = 0;
                for( int ptr=0; ptr<str.length(); ptr++) {
                    if( str.charAt(ptr) == current ) {
                        len++;
                        if( current == i )
                            current = j;
                        else
                            current = i;
                    }

                }
                if( i!=j ) len -= len%2;
                max = Math.max(len, max);
            }
        }
        System.out.println(str.length()-max);


    }

    boolean input() throws IOException
    {

        return true;
    }

    int[] niarr() throws IOException {
        String str = nline();
        String[] tokens = str.split(" ");
        int[] arr = new int[tokens.length];
        for( int i=0; i<arr.length; i++) {
            arr[i] = Integer.parseInt(tokens[i]);
        }
        return arr;
    }
}