#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 998244353;
void solve() {
  string S;
  cin >> S;
  int N = S.size();
  int cnt[10] = {};
  for (int i = (int)(0); i < (int)(N); ++i) {
    cnt[(int)S[i] - '0']++;
  }
  for (int i = (int)(0); i < (int)(10); ++i) {
    cnt[i] &= 1;
  }
  char t[N];
  for (int i = (int)(0); i < (int)(N); ++i) {
    if (i == 0 or i == N - 1)
      t[i] = '1';
    else
      t[i] = '0';
  }
  if (S <= t) {
    for (int i = (int)(0); i < (int)(N - 2); ++i) {
      cout << 9;
    }
    cout << endl;
    return;
  }
  for (int i = N - 1; i >= 0; i--) {
    int odd = 0;
    int ima = S[i] - '0';
    ima--;
    cnt[S[i] - '0'] ^= 1;
    for (int j = ima; j >= 0; j--) {
      cnt[j] ^= 1;
      int odd = 0;
      for (int k = (int)(0); k < (int)(10); ++k) {
        if (cnt[k]) odd++;
      }
      if (odd > N - 1 - i) {
        cnt[j] ^= 1;
        continue;
      }
      for (int k = N - 1; k > i; k--) {
        for (int l = (int)(0); l < (int)(10); ++l) {
          if (cnt[l] or l == 9) {
            cnt[l] ^= 1;
            S[k] = l + '0';
            break;
          }
        }
      }
      S[i] = j + '0';
      cout << S << endl;
      return;
    }
  }
}
int main() {
  int t;
  cin >> t;
  while (t--) solve();
}
