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.BufferedReader;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class C {
	private static Reader reader = new Reader();
	private static TokenReader tokenReader = new TokenReader();
	private static PrintWriter writer = new PrintWriter(System.out);

	public static void main(String[] args) throws IOException {
		int t = reader.readInt();
		while (t-- > 0) {
			char[] s = reader.readString().toCharArray();
			int n = s.length;
			ArrayList<Integer>[] idx = new ArrayList[10];
			for (int i = 0; i < 10; i++) {
				idx[i] = new ArrayList<>();
			}
			for (int i = 0; i < n; i++) {
				idx[s[i] - '0'].add(i);
			}
//			for (int i = 0; i < 10; i++) {
//				writer.println(i + " " + idx[i]);
//			}
			int min = Integer.MAX_VALUE;
			for (int i = 0; i < 10; i++) {
				for (int j = 0; j < 10; j++) {
					if (i == j) {
						min = Math.min(min, n - idx[i].size());
						continue;
					}
					if (idx[i].size() == 0 || idx[j].size() == 0) {
						continue;
					}
					int cur = idx[i].get(0);
					int len = 1;
					int id = j;
//					writer.println(i + " " + j);
					while (true) {
						int x = upper(idx[id], cur);
//						writer.println(x);
						if (x == idx[id].size()) {
							break;
						}
						cur = idx[id].get(x);
						len++;
						if (id == j) {
							id = i;
						} else {
							id = j;
						}
					}
//					writer.println("len = " + len);
					if (len % 2 == 1) len--;
					min = Math.min(min, n - len);
				}
			}
			writer.println(min);
 		}
		reader.close();
		writer.close();
	}
	
	static int upper(ArrayList<Integer> list, int x) {
    	int s = 0, e = list.size() - 1;
        int ans = list.size();
        while (s <= e) {
        	int mid = (s + e) / 2;
        	if (list.get(mid) > x) {
        		ans = mid;
        		e = mid - 1;
        	} else {
        		s = mid + 1;
        	}
        }
        return ans;
    }

	static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream input;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			this(System.in);
		}

		public Reader(String fileName) throws FileNotFoundException {
			this(new FileInputStream(fileName));
		}

		public Reader(InputStream inputStream) {
			input = new DataInputStream(inputStream);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readString() throws IOException {
			byte c = read();
			while (c <= ' ') {
				c = read();
			}
			StringBuilder string = new StringBuilder();
			do {
				if (Character.isValidCodePoint(c)) {
					string.appendCodePoint(c);
				}
				c = read();
			} while (!isWhitespace(c));
			return string.toString();
		}

		public int readInt() throws IOException {
			int result = 0;
			byte c = read();
			while (c <= ' ') {
				c = read();
			}
			boolean isNegative = (c == '-');
			if (isNegative) {
				c = read();
			}
			do {
				result = result * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (isNegative) {
				return -result;
			}
			return result;
		}

		public int[] readIntArray(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = readInt();
			}
			return a;
		}

		public long readLong() throws IOException {
			long result = 0;
			byte c = read();
			while (c <= ' ') {
				c = read();
			}
			boolean isNegative = (c == '-');
			if (isNegative) {
				c = read();
			}
			do {
				result = result * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (isNegative) {
				return -result;
			}
			return result;
		}

		public long[] readLongArray(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++) {
				a[i] = readLong();
			}
			return a;
		}

		public double readDouble() throws IOException {
			double result = 0, div = 1;
			byte c = read();
			while (c <= ' ') {
				c = read();
			}
			boolean isNegative = (c == '-');
			if (isNegative) {
				c = read();
			}
			do {
				result = result * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					result += (c - '0') / (div *= 10);
				}
			}
			if (isNegative) {
				return -result;
			}
			return result;
		}

		private boolean isWhitespace(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private void fillBuffer() throws IOException {
			bytesRead = input.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead) {
				fillBuffer();
			}
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (input == null) {
				return;
			}
			input.close();
		}

	}

	static class TokenReader {
		BufferedReader br;
		StringTokenizer st;

		public TokenReader(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

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

		public TokenReader(InputStream f) {
			br = new BufferedReader(new InputStreamReader(f));
		}

		String next() {
			if (hasMoreTokens()) {
				return st.nextToken();
			}
			return null;
		}

		boolean hasMoreTokens() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return false;
				st = new StringTokenizer(s);
			}
			return true;
		}

		int readInt() {
			return Integer.parseInt(next());
		}

		long readLong() {
			return Long.parseLong(next());
		}

		double readDouble() {
			return Double.parseDouble(next());
		}

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




