#include <bits/stdc++.h>
using namespace std;
char st[200010];
int n, m, c[200010][10];
void func() {
  for (int i = n; i >= 1; i--) {
    for (int j = st[i] - '0' - 1; j >= 0; j--) {
      if (i == 1 && j == 0) continue;
      int s = 0;
      for (int k = 0; k < 10; k++) s += c[i - 1][k] ^ (j == k);
      if (s <= n - i) {
        for (int k = 1; k < i; k++) putchar(st[k]);
        putchar(j + '0');
        for (int k = i + 1; k <= n - s; k++) putchar('9');
        for (int k = 9; k >= 0; k--)
          if (c[i - 1][k] ^ (j == k)) putchar(k + '0');
        putchar('\n');
        return;
      }
    }
  }
  for (int i = 1; i <= n - 2; i++) putchar('9');
  putchar('\n');
  return;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    scanf("%s", st + 1);
    n = strlen(st + 1);
    for (int i = 1; i <= n; i++) {
      int x = st[i] - '0';
      for (int ii = 0; ii < 10; ii++) c[i][ii] = c[i - 1][ii] ^ (ii == x);
    }
    func();
  }
  return 0;
}
