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

public class Main {
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long readLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }


    static class Pair {
        int x;
        int y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static int biggestDivisor(int n) {
        int max = 1;
        for(int i=2;i*i<=n;i++) {
            if(i*i == n) {
                if(i > max) {
                    max = i;
                }
            }
            else {
                if(n%i == 0) {
                    if(i > max) {
                        max = i;
                    }
                    if(n/i > max) {
                        max = n/i;
                    }
                }
            }
        }

        return max;
    }

    public static void main (String[] args)
    {
        InputReader in = new InputReader(System.in);
        int t = in.readInt();
        while(t != 0) {
            String st = in.readString();
            int max = 0;
            for(int i=0;i<10;i++) {
                for(int j=0;j<10;j++) {
                    int x = 0;
                    if(i == j) {
                        for(int k=0;k<st.length();k++) {
                            if(st.charAt(k) - '0' == i) {
                                x++;
                            }
                        }
                    }
                    else {
                        boolean f1 = false;
                        for(int k=0;k<st.length();k++) {
                            if(!f1) {
                                if(st.charAt(k) - '0' == i) {
                                    x++;
                                    f1 = true;
                                }
                            }
                            else {
                                if(st.charAt(k) - '0' == j) {
                                    x++;
                                    f1 = false;
                                }
                            }

                        }
                        if(x%2 == 1) {
                            x = x - 1;
                        }
                    }

                    if(x > max) {
                        max = x;
                    }
                }
            }

            System.out.println(st.length() - max);
            t--;
        }
    }


}