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 Main
{
    static PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
    static Scanner sc = new Scanner(System.in);
    static PrintStream ps = System.out;
    static int N = 200003, a[][] = new int[10][N], n, idx[] = new int[10]; 
	public static void main(String[] args)
	{
		int numCases = sc.nextInt();
		while (numCases --> 0)
		{
			Arrays.fill(idx, 0);
			int ans = 0;
			String s = sc.next();
			n = s.length();

			for (int [] r : a)
			{
				Arrays.fill(r, Integer.MAX_VALUE);
			}
			for (int i = 0; i < n; i++)
			{
				int m = s.charAt(i) - '0';
				a[m][idx[m]++] = i;
			}
			for (int i = 0; i < 10; i++)
			{
				ans = Math.max(ans, idx[i]);
			}
			int k = ans;
			for (int i = 0; i < 10; i++)
			{
				for (int j = 0; j < 10; j++)
				{
					if (i == j || idx[i] == 0 || idx[j] == 0) continue;
					int last = -1;
					// System.out.println(i + " " + j + " i j ");
					// for (int p = 0; p < idx[i]; p++)
					// {
					// 	ps.print(a[i][p] + " ");
					// }
					// ps.println();
					// for (int p = 0; p < idx[j]; p++)
					// {
					// 	ps.print(a[j][p] + " ");
					// }
					// ps.println();
					int p;
					for (p = 0; p <= k; p++)
					{

						if (last == -1)
						{
							last = 0;
						} else
						{
							last = -Arrays.binarySearch(a[i], a[j][last]) - 1;
							if (a[i][last] == Integer.MAX_VALUE)
							{
								// ans = Math.max(ans, p << 1);
								// ps.println(ans +"  out");

								break;
							}
						}

						// ps.println(a[i][last] + ",");
						last = -Arrays.binarySearch(a[j], a[i][last]) - 1;

						// if (last == -1) last = 0;
						// ps.println(a[j][last] + ";");
						if (a[j][last] == Integer.MAX_VALUE)
						{	

							// ans = Math.max(ans, p<< 1);
							// ps.println(ans +"  out");
							break;
						}
					}
					ans = Math.max(ans, p<< 1);
					// pw.println();
				}
			}
			pw.println(n - ans);
		}
		pw.close();
	}
}