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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static final long M = 1000000007;

    public static void main(String args[]) {

        FastReader io = new FastReader();

        int t  = io.nextInt();

        while(t > 0){
            String s = io.nextLine();

            System.out.println(new Solver().solve(s));

            t--;
        }
    }
}

class Solver{
    static final long MAX = 10000000000L;

    static final int M = 998244353;

    public int solve(String s){
       int count[][] = new int[s.length() + 1][10];
       int pre[][] = new int[s.length() + 1][10];

       ArrayList<Integer> oc[] = new ArrayList[10];

       for(int i = 0;i < 10;i++){
           oc[i] = new ArrayList<>();
       }

       for(int i = 0;i < s.length();i ++){
           count[i][s.charAt(i) - '0']++;

           oc[s.charAt(i) - '0'].add(i);
       }

       for(int i = 0;i < 10;i++){
           pre[0][i] = count[0][i];
           for(int j = 1;j < s.length();j++){
               pre[j][i] = pre[j - 1][i] + count[j][i];
           }
       }

//        for(int i = 0;i < 10;i++){
//            for(int j = 0;j < s.length();j++){
//               System.out.print(pre[j][i]);
//            }
//            System.out.println();
//        }

       int maxl = 0;

       for(int i = 0;i < 10;i++){

           int j = 0;

           maxl = Math.max(maxl,pre[s.length() - 1][i]);

           int hash[] = new int[10];

           while (j + 1 < oc[i].size()){

               for(int k = 0;k < 10;k++){
                   if(k == i)continue;

                   if(pre[oc[i].get(j + 1)][k] - pre[oc[i].get(j)][k] > 0){
                       hash[k]++;
                   }
               }

               j++;
           }

           for(int k = 0;k < 10;k++){
               if(k == i)continue;

               if(j < oc[i].size() && pre[s.length() - 1][k] - pre[oc[i].get(j)][k] > 0){
                   hash[k]++;
               }
           }

           for(int k = 0;k < 10; k++){
               maxl = Math.max(maxl,2*hash[k]);
           }
       }

       return s.length() - maxl;

    }




}

class Pair{
    char u,v;
    Pair(char u,char v){
        this.u = u;
        this.v = v;
    }
}

class CharStack {
    final StringBuilder sb = new StringBuilder();

    public void push(char ch) {
        sb.append(ch);
    }

    public char pop() {
        int last = sb.length() -1;
        char ch= sb.charAt(last);
        sb.setLength(last);
        return ch;
    }

    public int size() {
        return sb.length();
    }

    public boolean empty(){
        return (sb.length() == 0);
    }

    public char peek(){
        return sb.charAt(sb.length() - 1);
    }
    public  void  show(){
        System.out.println(sb);
    }
    public char[] get(){
        return  sb.toString().toCharArray();
    }
}

class DSU{
    int parent[] = new int[26];

    DSU(){
        for(int i = 0;i < 26; i++){
            parent[i] = -1;
        }
    }

    int getParent(int u){
        if(this.parent[u] == -1)
            return u;

        parent[u] = getParent(parent[u]);

        return parent[u];
    }

    void makeParent(int u,int v){
        int pu = getParent(u);
        int pv = getParent(v);

        parent[pu] = pv;
    }


}

class Util{
    static  final  long M = 998244353;
    static long modexp(long n,long m){
        if(m==0)
            return 1;
        else if(m==1)
            return n;
        else{
            long p = modexp(n,m/2);

            if(m%2==1)
                return (((p*p)%M)*n)%M;
            else
                return (p*p)%M;
        }
    }

    static  long exp(long n,long m){
        if(m == 0)
            return 1;
        if(m == 1)
            return n;

        long p = exp(n,m/2);

        if(m%2 == 1)
            return p*p*n;
        else
            return p*p;
    }

    static long gcd(long a,long b){
        if(a==0)
            return b;

        return gcd(b%a,a);
    }

    static long inv(long n){
        return modexp(n,M-2);
    }

    static long lcm(long a,long b){
        return a*b/gcd(a,b);
    }
    static long factorial(long fact[],long n){
        fact[0]=1;
        fact[1]=1;

        long prod = 1;

        for(int i = 2;i <= n;i++){
            prod = (prod*i)%M;

            fact[i] = prod;
        }

        return prod;
    }

    static boolean isPrime(long n){
        for(int i = 2;i*i <= n;i++){
            if(n%i == 0)
                return false;
        }
        return true;
    }
}

class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
        br = new BufferedReader(new
                InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            }
            catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

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

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        }
        catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}