#include <bits/stdc++.h>
using namespace std;
char s[200010];
int cnt[10];
int main() {
  int tt;
  scanf("%d", &tt);
  while (tt--) {
    scanf("%s", s);
    int n = (int)strlen(s);
    memset(cnt, 0, sizeof cnt);
    for (int i = 0; i < n; ++i) {
      ++cnt[s[i] - '0'];
    }
    bool can = false;
    for (int i = n - 1; i >= 0; --i) {
      int t = s[i] - '0';
      if (i == 0 && t == 1) {
        break;
      }
      --cnt[t];
      for (int nt = t - 1; nt >= 0; --nt) {
        ++cnt[nt];
        int rem = n - i - 1;
        bool ok = true;
        for (int j = 0; j < 10; ++j) {
          if (cnt[j] % 2 == 1) {
            if (rem == 0) {
              ok = false;
              break;
            }
            --rem;
          }
        }
        if (ok && rem % 2 == 0) {
          for (int j = 0; j < i; ++j) {
            putchar(s[j]);
          }
          putchar((char)('0' + nt));
          for (int j = 0; j < rem; ++j) {
            putchar('9');
          }
          for (int j = 9; j >= 0; --j) {
            if (cnt[j] % 2 == 1) {
              putchar((char)('0' + j));
            }
          }
          putchar('\n');
          can = true;
          break;
        }
        --cnt[nt];
      }
      if (can) {
        break;
      }
    }
    if (!can) {
      for (int i = 0; i < n - 2; ++i) {
        putchar('9');
      }
      putchar('\n');
    }
  }
}
