#include <bits/stdc++.h>
using namespace std;
int T, N;
string S;
string decdec(string A) {
  for (int i = A.size() - 1; i >= 0; i--) {
    if (A[i]-- != '0') break;
    A[i] = '9';
  }
  A = A.substr(A[0] == '0');
  if (A.empty()) A = "0";
  return A;
}
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> T;
  while (T--) {
    cin >> S;
    S = decdec(S);
    N = S.size();
    if (N % 2 == 1) {
      for (i = 0; i < (N - 1); i++) cout << 9;
      cout << endl;
      continue;
    }
    if (S[0] == '1' && count((S.begin()), (S.end()), '0') == N - 1) {
      for (i = 0; i < (N - 2); i++) cout << 9;
      cout << endl;
      continue;
    }
    int mask = 0;
    for (auto& c : S) mask ^= 1 << (c - '0');
    if (mask == 0) {
      cout << S << endl;
      continue;
    }
    for (i = 0; i < (N); i++) {
      mask ^= 1 << (S[N - 1 - i] - '0');
      for (j = S[N - 1 - i] - '0' - 1; j >= 0; j--) {
        int mask2 = mask ^ (1 << j);
        if (__builtin_popcount(mask2) <= i &&
            (i - __builtin_popcount(mask2)) % 2 == 0) {
          S[N - 1 - i] = j + '0';
          for (j = i - 1; j >= 0; j--) {
            if (j + 1 > __builtin_popcount(mask2)) {
              S[N - 1 - j] = '9';
            } else {
              for (x = 9; x >= 0; x--)
                if (mask2 & (1 << x)) {
                  S[N - 1 - j] = x + '0';
                  mask2 ^= 1 << x;
                  break;
                }
            }
          }
          i = N;
          break;
        }
      }
    }
    cout << S << endl;
  }
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  cout.tie(0);
  solve();
  return 0;
}
