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;
void vp(vector<long long> &v);
vector<long long> prime;
bitset<000000 + 1> isPrime;
vector<long long> primeFactor;
vector<long long> uniqueprimeFactor;
vector<long long> divisors[000000 + 1];
vector<long long> divNum;
long long phiValue[000000 + 5];
void seive(long long lim);
void primeFactorial(long long n);
void eulerPhi(long long lim);
void divGenerator(long long n);
void div(long long n);
long long bigMod(long long b, long long p, long long m);
long long nCr(long long n, long long r);
long long string2int(string str);
long long gcd(long long a, long long b);
long long lcm(long long a, long long b);
string int2string(long long num);
long long bs(long long arr[], long long l, long long r, long long x);
long long prevMatch(long long arr[], long long l, long long r, long long x);
long long range(long long arr[], long long l, long long r, long long left,
                long long right);
long long firstMarched(long long arr[], long long l, long long r, long long x);
long long vbs(vector<long long> &arr, long long l, long long r, long long x);
long long vprevMatch(vector<long long> &arr, long long l, long long r,
                     long long x);
long long vrange(vector<long long> &arr, long long l, long long r,
                 long long left, long long right);
long long vfirstMarched(vector<long long> &arr, long long l, long long r,
                        long long x);
vector<long long> LIS;
void flis(long long arr[], long long n);
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long test = 1;
  cin >> test;
  for (long long cas = 1; cas <= test; ++cas) {
    string str;
    cin >> str;
    long long mx = 0;
    for (long long i = 0; i <= 9; ++i) {
      for (long long j = 0; j <= 9; ++j) {
        if (i != j) {
          char a = (char)(i + 48), b = (char)(j + 48);
          bool ck = false;
          long long cnt = 0;
          for (long long k = 0; k < (long long)str.size(); ++k) {
            if (str[k] == a && ck == false) {
              ck = true;
            } else if (ck == true && str[k] == b) {
              ck = false;
              cnt++;
            }
          }
          mx = max(mx, cnt);
        }
      }
    }
    mx *= 2;
    map<char, long long> m;
    for (long long i = 0; i < (long long)str.size(); ++i) {
      m[str[i]] += 1;
    }
    for (auto i : m) {
      if (i.second > mx) {
        mx = i.second;
      }
    }
    cout << (long long)str.size() - mx << endl;
  }
  return 0;
}
void vp(vector<long long> &v) {
  long long val;
  cin >> val;
  v.push_back(val);
}
long long gcd(long long a, long long b) {
  if (a % b == 0) {
    return b;
  }
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
  long long ret = ((a / gcd(a, b)) * b);
  return ret;
}
void seive(long long lim) {
  isPrime.set();
  prime.push_back(2);
  for (long long i = 3; i <= lim; i += 2) {
    if (isPrime[i]) {
      prime.push_back(i);
      for (long long j = i * i; j <= lim; j += (i << 1)) {
        isPrime[j] = 0;
      }
    }
  }
}
void primeFactorial(long long n) {
  for (long long i = 0; prime[i] * prime[i] <= n; i++) {
    long long cnt = 0;
    while (n % prime[i] == 0) {
      n = n / prime[i];
      cnt++;
      primeFactor.push_back(prime[i]);
    }
    if (cnt > 0) {
      uniqueprimeFactor.push_back(prime[i]);
    }
    if (n == 1) {
      break;
    }
  }
  if (n > 1) {
    primeFactor.push_back(n);
    uniqueprimeFactor.push_back(n);
  }
}
void eulerPhi(long long lim) {
  for (long long i = 0; i <= lim; ++i) {
    phiValue[i] = i;
  }
  for (long long i = 2; i <= lim; ++i) {
    if (phiValue[i] == i) {
      for (long long j = i; j <= lim; j += i) {
        phiValue[j] = (phiValue[j] * (i - 1)) / i;
      }
    }
  }
  phiValue[0] = 1;
  phiValue[1] = 1;
}
long long bigMod(long long b, long long p, long long m) {
  long long y;
  if (b == 0) {
    return 0;
  }
  if (p == 0) {
    return 1;
  }
  if (p % 2 == 0) {
    y = bigMod(b, p / 2, m);
    y = (y * y) % m;
  } else {
    y = b % m;
    y = (y * bigMod(b, p - 1, m) % m) % m;
  }
  return (y + m) % m;
}
long long nCr(long long n, long long r) {
  long long p = 1, k = 1;
  if (n - r < r) {
    r = n - r;
  }
  if (r != 0) {
    while (r) {
      p *= n;
      k *= r;
      long long m = gcd(p, k);
      p /= m;
      k /= m;
      n--;
      r--;
    }
  } else {
    p = 1;
  }
  return p;
}
void divGenerator(long long n) {
  for (long long i = 1; i <= n; i++) {
    for (long long j = i; j <= n; j += i) {
      divisors[j].push_back(i);
    }
  }
}
long long string2int(string str) {
  long long cnt = 1, sum = 0;
  for (long long i = str.length() - 1; i >= 0; i--) {
    long long typcast = (int)(str[i]) - 48;
    sum = sum + typcast * cnt;
    cnt = cnt * 10;
  }
  return sum;
}
string int2string(long long num) {
  string str = "";
  while (num > 0) {
    int ch;
    ch = ((num) % 10) + 48;
    str += char(ch);
    num = num / 10;
  }
  reverse(str.begin(), str.end());
  if (str.empty()) {
    str = "0";
  }
  return str;
}
void div(long long n) {
  for (long long i = 1; i * i <= n; ++i) {
    if (n % i == 0) {
      if (i != (n / i)) {
        divNum.push_back(i);
        divNum.push_back(n / i);
      } else {
        divNum.push_back(i);
      }
    }
  }
  sort(divNum.begin(), divNum.end());
}
long long bs(long long arr[], long long l, long long r, long long x) {
  long long m;
  while (l <= r) {
    m = (l + r) / 2;
    if (arr[m] == x) {
      return m;
    } else if (arr[m] < x) {
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  return -1;
}
long long vbs(vector<long long> &arr, long long l, long long r, long long x) {
  long long m;
  while (l <= r) {
    m = (l + r) / 2;
    if (arr[m] == x) {
      return m;
    } else if (arr[m] < x) {
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  return -1;
}
long long prevMatch(long long arr[], long long l, long long r, long long x) {
  long long m, ret = -1;
  while (l <= r) {
    m = (l + r) / 2;
    if (arr[m] <= x) {
      ret = m;
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  return ret;
}
long long vprevMatch(vector<long long> &arr, long long l, long long r,
                     long long x) {
  long long m, ret = -1;
  while (l <= r) {
    m = (l + r) / 2;
    if (arr[m] <= x) {
      ret = m;
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  return ret;
}
long long range(long long arr[], long long l, long long r, long long left,
                long long right) {
  long long ret;
  ret = prevMatch(arr, l, r, right) - prevMatch(arr, l, r, left - 1);
  return ret;
}
long long vrange(vector<long long> &arr, long long l, long long r,
                 long long left, long long right) {
  long long ret;
  ret = vprevMatch(arr, l, r, right) - vprevMatch(arr, l, r, left - 1);
  return ret;
}
long long firstMarched(long long arr[], long long l, long long r, long long x) {
  long long m, ret = -1;
  while (l <= r) {
    m = (l + r) / 2;
    if (arr[m] == x) {
      ret = m;
      r = m - 1;
    } else if (arr[m] < x) {
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  return ret;
}
long long vfirstMarched(vector<long long> &arr, long long l, long long r,
                        long long x) {
  long long m, ret = -1;
  while (l <= r) {
    m = (l + r) / 2;
    if (arr[m] == x) {
      ret = m;
      r = m - 1;
    } else if (arr[m] < x) {
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  return ret;
}
void flis(long long arr[], long long n) {
  long long parent[n], increasingSub[n + 1], length = 0;
  for (long long i = 0; i < n; ++i) {
    long long low = 1, high = length;
    while (low <= high) {
      long long mid = ceil((double)(low + high) / 2.0);
      if (arr[increasingSub[mid]] <= arr[i]) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    long long pos = low;
    parent[i] = increasingSub[pos - 1];
    increasingSub[pos] = i;
    if (pos > length) {
      length = pos;
    }
  }
  long long k = increasingSub[length];
  for (long long i = length - 1; i >= 0; i--) {
    LIS.push_back(arr[k]);
    k = parent[k];
  }
  reverse(LIS.begin(), LIS.end());
}
