#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int dxx[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
          dyy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const long long mod = 1000000007;
const int base = 311;
int n, cnt[10], used[10];
string s;
void answer(int idx) {
  for (int i = 1; i <= idx; ++i) cout << s[i];
  for (int i = idx + 1, cur = 9; i <= n; ++i) {
    while (used[cur] == 0) --cur;
    cout << cur;
    --used[cur];
  }
  cout << '\n';
}
void gogo() {
  cin >> s;
  n = ((int)(s).size());
  s = ' ' + s;
  for (int i = 0; i <= 9; ++i) cnt[i] = 0;
  for (int i = 1; i <= n; ++i) {
    ++cnt[s[i] - '0'];
  }
  for (int i = n; i >= 1; --i) {
    int lim = s[i] - '0';
    --cnt[lim];
    for (int j = lim - 1; j >= (i == 1 ? 1 : 0); --j) {
      ++cnt[j];
      int can_change = n - i;
      for (int k = 0; k <= 9; ++k) used[k] = 0;
      int check = 1;
      for (int k = 0; k <= 9; ++k) {
        if (cnt[k] % 2 == 0) continue;
        if (can_change == 0) {
          check = 0;
          break;
        }
        --can_change;
        ++used[k];
      }
      --cnt[j];
      if (can_change % 2 == 1 || !check) continue;
      used[9] += can_change;
      s[i] = char(j + '0');
      answer(i);
      return;
    }
  }
  for (int i = 1; i <= n - 2; ++i) cout << "9";
  cout << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if (fopen("sol"
            ".inp",
            "r")) {
    freopen(
        "sol"
        ".inp",
        "r", stdin);
    freopen(
        "sol"
        ".out",
        "w", stdout);
  }
  int t;
  cin >> t;
  while (t--) gogo();
}
