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 A {

	static PrintWriter out;
	
	static class FIO {
		BufferedReader in;
		StringTokenizer st = null;
		FIO() throws IOException{
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			st = null;
		}
		FIO(String s) throws IOException {
			in = new BufferedReader(new FileReader(s + ".in"));
			out = new PrintWriter(new FileWriter(s + ".out"));
			st = null;
		}
		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(in.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());
		}
	}
	static FIO in;
	public static void main(String[] args) throws IOException {
		in = new FIO();
		int tc = in.nextInt();
		while (tc-- > 0)
			new solver();
		
		out.close();
		
	}
	static class solver {
		void p1() {
			out.println("WIN");
		}
		void p2() {
			out.println("LOSE");
		}
		solver() {
			String s = in.next();
			int N = s.length();
			int[] ar = new int[s.length()];
			for (int i = 0; i < s.length(); ++i) {
				ar[i] = s.charAt(i) - '0';
			}
			int res = 0;
			int[] oc = new int[10];
			for (int i = 0; i < N; ++i) {
				oc[ar[i]]++;
			}
			for (int i = 0; i < 10; ++i)
				res = Math.max(res, oc[i]);
			
			for (int i = 0; i < 10; ++i) {
				for (int j = i + 1; j < 10; ++j) {
					Queue<Integer> q = new LinkedList<>();
					for (int k = 0; k < N; ++k) {
						if (ar[k] == i || ar[k] == j)
							q.add(ar[k]);
					}
					int cur = 0, let = -1;
					while (!q.isEmpty()) {
						int x = q.peek();
						q.poll();
						if (x != let) {
							let = x;
							cur++;
						}
					}
					cur -= (cur%2);
					res = Math.max(res, cur);
				}
			}
			out.println((N - res));
		}
		
	}
	

}
/*
1
4
1 0 1 6




 
*/
