#include <bits/stdc++.h>
using namespace std;
const int maxn = 201015;
const int maxk = 58500;
const int maxe = maxn * 2;
const long long mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int n, m;
char str[maxn];
int cou[maxn][10];
void func() {
  for (int i = n; i >= 1; i--) {
    for (int j = str[i] - '0' - 1; j >= 0; j--) {
      if (i == 1 && j == 0) continue;
      int lef = 0;
      for (int k = 0; k < 10; k++) {
        lef += cou[i - 1][k] ^ (j == k);
      }
      if (lef <= n - i) {
        for (int k = 1; k < i; k++) {
          putchar(str[k]);
        }
        putchar(j + '0');
        for (int k = i + 1; k <= n - lef; k++) putchar('9');
        for (int k = 9; k >= 0; k--)
          if (cou[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;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", str + 1);
    n = strlen(str + 1);
    for (int i = 1; i <= n; i++) {
      int idx = str[i] - '0';
      for (int ii = 0; ii < 10; ii++) cou[i][ii] = cou[i - 1][ii] ^ (ii == idx);
    }
    func();
  }
  return 0;
}
