#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, m, z, x, y, cnt[10], a[N], flag, wr[15];
long long f[2][15][1100];
char s[N];
bool check(int a, int b) {
  int tmp = z;
  if (cnt[b] % 2 == 0)
    tmp += 1;
  else
    tmp -= 1;
  if (tmp <= a)
    return true;
  else
    return false;
}
void work() {
  int len = strlen(s);
  for (int i = 0; i < len; ++i) a[i] = s[len - i - 1] - '0';
  --a[0];
  int x = 0;
  while (a[x] < 0) {
    a[x] += 10;
    ++x;
    --a[x];
  }
  if (len <= 4) {
    int z = 0, tmp, zt;
    for (int i = 0; i < len; ++i) z = z * 10 + s[i] - '0';
    --z;
    for (int i = z; i >= 0; --i)
      if (z >= 1000 || z <= 99) {
        zt = 0;
        tmp = i;
        while (tmp > 0) zt = zt ^ (1 << (tmp % 10)), tmp /= 10;
        if (zt == 0) {
          printf("%d\n", i);
          return;
        }
      }
  }
  flag = 0;
  if (a[len - 1] > 1) flag = 1;
  for (int i = 0; i < len - 1; ++i)
    if (a[i] != 0) flag = 1;
  if (flag == 0 || a[len - 1] <= 0) {
    for (int i = 0; i < len - 2; ++i) printf("9");
  } else {
    int zt = 0, w = min(len - 1, 11);
    for (int i = 12; i < len; ++i) zt ^= (1 << a[i]);
    for (int i = w + 1; i >= 0; --i)
      for (int j = 0; j < (1 << 10); ++j) f[0][i][j] = f[1][i][j] = -1;
    f[0][w + 1][zt] = 0;
    for (int i = w; i >= 0; --i) {
      for (int j = 0; j < (1 << 10); ++j) {
        if (f[0][i + 1][j] != -1) {
          f[0][i][j ^ (1 << a[i])] = f[0][i + 1][j] * 10 + a[i];
          for (int k = a[i] - 1; k >= 0; --k)
            f[1][i][j ^ (1 << k)] =
                max(f[1][i][j ^ (1 << k)], f[0][i + 1][j] * 10 + k);
        }
        if (f[1][i + 1][j] != -1)
          for (int k = 9; k >= 0; --k)
            f[1][i][j ^ (1 << k)] =
                max(f[1][i][j ^ (1 << k)], f[1][i + 1][j] * 10 + k);
      }
    }
    for (int i = len - 1; i >= 12; --i) printf("%d", a[i]);
    long long b = max(f[0][0][0], f[1][0][0]);
    for (int i = 0; i <= w; ++i) {
      wr[i] = b % 10;
      b /= 10;
    }
    for (int i = w; i >= 0; --i) printf("%d", wr[i]);
  }
  printf("\n");
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s);
    work();
  }
}
