#include <bits/stdc++.h>
using namespace std;
char res[200005 + 1];
char s[200005 + 1];
int cif[200005 + 1][10];
int now[10];
int add[10];
int N;
int main() {
  int i, j, k, cnt, remain, gata, fuck, T, ok;
  scanf("%d\n", &T);
  while (T--) {
    scanf("%s\n", &s);
    N = strlen(s);
    for (i = 0; i < N; ++i) res[i] = s[i];
    res[N] = '\0';
    for (i = N; i >= 1; --i) s[i] = s[i - 1] - '0';
    for (i = 1; i <= N; ++i) {
      for (j = 0; j <= 9; ++j) cif[i][j] = cif[i - 1][j];
      ++cif[i][s[i]];
    }
    gata = 0;
    for (i = N; i >= 1; --i) {
      for (j = 0; j <= 9; ++j) now[j] = cif[i - 1][j];
      fuck = (i == 1);
      for (j = s[i] - 1; j >= fuck; --j) {
        ++now[j];
        remain = N - i;
        memset(add, 0, sizeof(add));
        for (k = 0; k <= 9 && remain; ++k)
          if (now[k] % 2) --remain, ++add[k];
        ok = 1;
        for (k = 0; k <= 9; ++k)
          if ((now[k] + add[k]) % 2) ok = 0;
        if (ok && (remain % 2 == 0)) {
          gata = 1;
          break;
        } else
          --now[j];
      }
      if (gata) {
        cnt = i;
        res[i - 1] = '0' + j;
        for (j = 1; j <= remain; ++j) res[cnt++] = '9';
        for (j = 9; j >= 0; --j)
          if (add[j]) res[cnt++] = '0' + j;
        break;
      }
    }
    if (!gata)
      for (i = 0; i < N - 2; ++i) res[i] = '9';
    if (!gata) res[N - 2] = '\0';
    printf("%s\n", res);
  }
  return 0;
}
