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 LeetCode;

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

public class Main {

	static class Reader {
		BufferedReader br;
		StringTokenizer st;

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

		public int nextInt() throws IOException {
			if (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return Integer.parseInt(st.nextToken());
		}

		public float nextFloat() throws IOException {
			if (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return Float.parseFloat(st.nextToken());
		}

		public long nextLong() throws IOException {
			if (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return Long.parseLong(st.nextToken());
		}

		public double nextDouble() throws IOException {
			if (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return Double.parseDouble(st.nextToken());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return st.nextToken();
		}
	}

	static int mod = (int) (1e9 + 7);

	public static void main(String[] args) throws IOException {
		Reader sc = new Reader();
		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		try {
			int t = sc.nextInt();
			while (t-- > 0) {
				int count[] = new int[10];
				String str = sc.next();
				for(int i=0;i<str.length();i++)
					count[str.charAt(i)-'0']++;
				int max=0;
				for(int i=0;i<=9;i++) {
					if(count[i]>max) {
						max = count[i];
					}
				}
				for(int i=0;i<=9;i++) {
					for(int j=0;j<=9;j++) {
						if(i==j)
							continue;
						int curr = 0;
						int len = 0;
						for(int k=0;k<str.length();k++) {
							if(curr==0) {
								if(str.charAt(k)-'0'==i) {
									len++;
									curr = 1 - curr;
								}
							} else {
								if(str.charAt(k)-'0'==j) {
									len++;
									curr = 1 - curr;
								}
							}
						}
						if((len&1)!=0)
							len--;
						if(len>max) {
//							System.out.println(i+" "+j+" "+len);
							max = len;
						}
					}
				}
				out.println(str.length()-max);
			}
			out.flush();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	static class Pair implements Comparable<Pair> {
		long first;
		long second;

		public Pair(long first, long second) {
			this.first = first;
			this.second = second;
		}

		@Override
		public int compareTo(Pair o) {
			if (this.first > o.first) {
				return -1;
			} else if (this.first < o.first) {
				return 1;
			} else {
				return 0;
			}
		}
	}

	static class Pair2 {
		int first, second;

		public Pair2(int first, int second) {
			this.first = first;
			this.second = second;
		}
	}
}