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.
#include <bits/stdc++.h>
using namespace ::std;
template <class T>
T SQR(T N) {
  return (T)N * N;
}
template <class T>
double DIST(T a, T b) {
  return 1.0 * sqrt(SQR(double(a)) + SQR(double(b)));
}
template <class T>
bool CROSS(pair<T, T> a, pair<T, T> b, pair<T, T> c) {
  return (b.first - a.first) * (c.second - b.second) >=
         (b.second - a.second) * (c.first - b.first);
}
int px[] = {0, 1, -1, 0, -1, -1, 1, 1};
int py[] = {1, 0, 0, -1, -1, 1, -1, 1};
double EPS = 1e-9;
double PI = acos(-1);
double GR = 1.6180339887498948;
vector<int> Pr;
inline void Seive() {
  bool a[15007]{};
  Pr.push_back(2);
  for (int i = 4; i <= 15005; i += 2) a[i] = 1;
  for (long long i = 3; i * i < (1505); i += 2)
    if (!a[i]) {
      for (long long j = i * i; j <= 15005; j = j + 2 * i) a[j] = 1;
    }
  for (int i = 3; i <= 15005; i += 2)
    if (!a[i]) Pr.push_back(i);
}
inline long long power(long long a, long long p, long long mod) {
  long long x = a, res = 1;
  while (p) {
    if (p & 1) res = (res * x) % mod;
    p /= 2, x = (x * x) % mod;
  }
  return res;
}
int F[207];
inline void Fail(string str) {
  string s = str;
  reverse(s.begin(), s.end());
  s = s + "#" + str;
  int len = s.length();
  for (int i = 1; i < len; ++i) {
    int j = F[i - 1];
    while (j > 0 and s[i] != s[j]) j = F[j - 1];
    if (s[i] == s[j]) ++j;
    F[i] = j;
  }
}
int main() {
  cin.tie(0);
  cout.tie(0);
  int n, m, c, d, a, b, k;
  int test;
  scanf("%d", &test);
  for (int t = 1; t <= test; ++t) {
    string str;
    cin >> str;
    n = str.length();
    int res = n;
    for (char i = '0'; i <= '9'; ++i)
      for (char j = '0'; j <= '9'; ++j) {
        int cnt1 = 0;
        int cnt2 = 0;
        a = 0;
        for (int l = 0; l < n; ++l) {
          if (a == 0 and str[l] == i)
            a = 1;
          else if (str[l] == j and a == 1)
            a = 0, cnt1 += 2;
          cnt2 += (str[l] == i);
        }
        res = min(res, min(n - cnt1, n - cnt2));
      }
    printf("%d\n", res);
  }
}
