#include <bits/stdc++.h>
using namespace std;
int i, j, k, l, s, n, m, a[200005], ans[200005], test;
long long A[200005];
char c[200005];
inline bool check(int x, int y, int z) {
  z ^= (1 << (y));
  long long s = 0;
  for (int i = 0; i <= 9; i++, z >>= 1)
    if (z & 1) s = s * 10 + i;
  return s <= A[x];
}
inline bool check1(int x, int y, int z) {
  z ^= (1 << (y));
  long long s = 0;
  for (int i = 0; i <= 9; i++, z >>= 1) s += (z & 1);
  return s <= n - x + 1;
}
inline void dfs(int x, int y, int z) {
  if (x > n) return;
  if (y) {
    for (int i = 9; i >= 0; i--)
      if (check1(x + 1, i, z)) {
        ans[x] = i;
        dfs(x + 1, y, z ^ (1 << (i)));
        return;
      }
  } else {
    if (check(x + 1, a[x], z)) {
      ans[x] = a[x];
      dfs(x + 1, 0, z ^ (1 << (a[x])));
      return;
    }
    for (int i = a[x] - 1; i >= 0; i--)
      if (check1(x + 1, i, z)) {
        ans[x] = i;
        dfs(x + 1, 1, z ^ (1 << (i)));
        return;
      }
  }
}
int main() {
  scanf("%d", &test);
  while (test--) {
    scanf("%s", c + 1);
    n = strlen(c + 1);
    for (i = 1; i <= n; i++) a[i] = c[i] - 48;
    if (n & 1) {
      for (i = 1; i < n; i++) putchar('9');
      puts("");
      continue;
    }
    a[n]--;
    i = n;
    while (a[i] < 0) a[i] += 10, a[--i]--;
    if (a[1] == 0) {
      for (i = 1; i < n - 1; i++) putchar('9');
      puts("");
      continue;
    }
    long long s = 1;
    A[n + 1] = 0;
    for (i = n; i; i--) {
      A[i] = A[i + 1] + a[i] * s;
      A[i] = min(A[i], 10000000000000ll);
      s = min(s * 10, 10000000000000ll);
    }
    dfs(1, 0, 0);
    if (ans[1]) {
      for (i = 1; i <= n; i++) printf("%d", ans[i]);
    } else {
      for (i = 2; i < n; i++) printf("%d", ans[i]);
    }
    puts("");
  }
}
