#include <bits/stdc++.h>
const long long INFLL = 1e18;
using namespace std;
int calcBits(int x) {
  int cnt = 0;
  while (x > 0) {
    cnt += x & 1;
    x >>= 1;
  }
  return cnt;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int n = (int)s.size();
    int m1 = 0;
    for (auto ch : s) {
      m1 ^= (1 << (ch - '0'));
    }
    int m2 = 0;
    for (int i = n - 1; i >= 0; i--) {
      for (int j = 1; j <= s[i] - '0'; j++) {
        m1 ^= (1 << (s[i] - '0'));
        m1 ^= (1 << (s[i] - j - '0'));
        int curMask = m1 ^ m2;
        int cnt = calcBits(curMask);
        if (cnt <= n - i - 1) {
          if (curMask & (1 << 9)) {
            --cnt;
          }
          if ((n - i - 1 - cnt) % 2 == min(1, (curMask & (1 << 9)))) {
            string t = "";
            for (int j = 0; j < i; j++) {
              t += s[j];
            }
            s[i] -= j;
            t += s[i];
            for (int j = i + 1; j < n; j++) {
              t += "9";
            }
            int ptr = n - 1;
            for (int j = 0; j < 9; j++) {
              if ((1 << j) & curMask) {
                t[ptr] = '0' + j;
                --ptr;
              }
            }
            if (t[0] == '0') {
              t.erase(t.begin());
              t.erase(t.end() - 1);
            }
            cout << t << "\n";
            goto end;
          }
        }
        m1 ^= (1 << (s[i] - '0'));
        m1 ^= (1 << (s[i] - j - '0'));
      }
      m2 ^= (1 << (s[i] - '0'));
    }
  end:;
  }
  return 0;
}
