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.
//package codeforces.educational_92;

import java.io.*;
import java.util.StringTokenizer;

public class _e92_C {

    public static void main (String[] args) throws Exception {

        String s = "3\n" +
                "95831\n" +
                "100120013\n" +
                "252525252525";

//        String s = "1\n" +
//                "252525252525";

//        br = new BufferedReader(new StringReader(s));
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        rl(); int T = nin();
        next_test:
        for (int t=1; t<=T; ++t) {
            rl(); char[] S = nca(); int n=S.length;
            int maxS[] = new int[10];
            for (int i=0; i<n; ++i) {
                ++maxS[S[i]-48];
            }
            int maxUnion = 0;
            for (int i=0; i<10; ++i) {
                maxUnion = Math.max(maxUnion, maxS[i]);
            }

            int maxSwitch = 0;
            for (char a='0'; a<='8'; ++a) {
                for (char b=(char)(a+1); b<='9'; ++b) {
                    int c='X'; int count = 0;
                    for (int i=0; i<n; ++i) {
                        if ((S[i]==a || S[i] == b) && S[i]!=c) {
                            ++count; c=S[i];
                        }
                    }
                    maxSwitch = Math.max(count, maxSwitch);
                }
            }
            maxSwitch -= maxSwitch%2;
            int min = Math.min(n-maxSwitch, n-maxUnion);

            bw.write(Integer.toString(min));
            bw.newLine();
        }
        bw.flush();
    }

    static BufferedReader br; static BufferedWriter bw; static StringTokenizer st;
    static void rl() throws Exception{ st = new StringTokenizer(br.readLine()); }
    static long nlo(){ return Long.parseLong(st.nextToken()); }
    static int nin(){ return Integer.parseInt(st.nextToken()); }
    /*private static void te(){}*/
    static double ndo(){ return Double.parseDouble(st.nextToken()); }
    static char[] nca(){ return st.nextToken().toCharArray(); }
}
