#include <bits/stdc++.h>
using namespace std;
int nrt, n, par[200005][11], f[11], sumf;
char sir[200005];
bool nuamsol() {
  if (sir[0] != '1') return 0;
  for (int i = 1; i < n - 1; i++)
    if (sir[i] != '0') return 0;
  if (sir[n - 1] > '1') return 0;
  return 1;
}
bool ok(int poz, int cif) {
  int i, aux;
  sumf = 0;
  for (i = 0; i <= 9; i++) f[i] = 0;
  if (poz > 0) {
    for (i = 0; i <= 9; i++) f[i] = par[poz - 1][i];
  }
  f[cif] ^= 1;
  for (i = 0; i <= 9; i++) sumf += f[i];
  aux = n - (poz + 1);
  if (aux >= sumf)
    return 1;
  else
    return 0;
}
void modif(int poz, int cif) {
  int i, j = 0;
  sir[poz] = cif + '0';
  for (i = n - 1; (i >= poz + 1) && (j <= 9);) {
    while ((f[j] == 0) && (j <= 9)) j++;
    if (j <= 9) {
      sir[i] = j + '0';
      j++;
      i--;
    } else
      break;
  }
  for (; i >= poz + 1; i--) sir[i] = '9';
}
void solutie() {
  int i, j;
  for (i = 0; i <= 9; i++) par[0][i] = 0;
  par[0][sir[0] - '0'] ^= 1;
  for (i = 1; i < n; i++) {
    for (j = 0; j <= 9; j++) par[i][j] = par[i - 1][j];
    par[i][sir[i] - '0'] ^= 1;
  }
  for (int i = n - 1; i >= 0; i--)
    for (int cif = sir[i] - 1 - '0'; cif >= 0; cif--)
      if (ok(i, cif)) {
        modif(i, cif);
        cout << sir << "\n";
        return;
      }
}
int main() {
  cin >> nrt;
  while (nrt--) {
    cin >> sir;
    n = strlen(sir);
    if (nuamsol()) {
      for (int i = 1; i <= n - 2; i++) cout << '9';
      cout << "\n";
    } else
      solutie();
  }
  return 0;
}
