#include <bits/stdc++.h>
using namespace std;
void solve() {
  string s;
  long long cnt[10] = {0}, i = 0, n, j, k;
  cin >> s;
  n = s.length();
  for (i = 0; i < n; i++) {
    cnt[s[i] - '0']++;
  }
  if (s[0] == '1' && ((s[n - 1] == '0' && cnt[0] >= n - 1) ||
                      (s[n - 1] == '1' && cnt[0] >= n - 2))) {
    for (i = 0; i < n - 2; i++) cout << 9;
    cout << endl;
    return;
  } else {
    for (i = n - 1; i >= 0; i--) {
      cnt[s[i] - '0']--;
      for (j = s[i] - '0' - 1; j >= 0; j--) {
        cnt[j]++;
        long long res = 0;
        for (k = 0; k < 10; k++) res += (cnt[k] & 1);
        if (res <= n - i) {
          for (k = 0; k < i; k++) cout << s[k];
          cout << j;
          for (k = i + 1; k < n - res; k++) cout << 9;
          for (k = 9; k >= 0; k--)
            if ((cnt[k] & 1)) cout << k;
          cout << endl;
          return;
        }
        cnt[j]--;
      }
    }
  }
}
int main(void) {
  long long n, i = 0;
  for (cin >> n; i < n; i++) solve();
  return 0;
}
