#include <bits/stdc++.h>
using namespace std;
long long int power(long long int x, long long int y, long long int p) {
  long long int r = 1;
  x = x % p;
  while (y) {
    if (y & 1) r = r * x % p;
    y = y >> 1;
    x = x * x % p;
  }
  return r;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int csrand(int l = 0, int r = 1e9) {
  uniform_int_distribution<int> uid(l, r);
  return uid(rng);
}
const int N = 2e5 + 99;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t0;
  cin >> t0;
  while (t0--) {
    string s;
    cin >> s;
    if (s[0] == '1') {
      int tk = 1;
      for (int i = 1; i < s.length(); i++)
        if (s[i] != '0') tk = 0;
      if (tk) {
        for (int i = 0; i < s.length() - 2; i++) cout << 9;
        cout << '\n';
        continue;
      }
    }
    int mask = 0;
    for (int i = 0; i < s.length(); i++) mask ^= 1 << (s[i] - '0');
    int tk = 0;
    string ans;
    for (int i = s.length() - 1; i >= 0; i--) {
      mask ^= (1 << (s[i] - '0'));
      bitset<10> aa = mask;
      for (int j = s[i] - '1'; j >= 0; j--) {
        int cur = mask ^ (1 << j);
        int kk = __builtin_popcount(cur);
        int rem = s.length() - i - 1;
        if (rem >= kk) {
          tk = 1;
          ans = s.substr(0, i);
          ans += char(j + '0');
          for (int j = 0; j < rem - kk; j++) ans += '9';
          for (int k = 9; k >= 0; k--)
            if (cur & (1 << k)) ans += char(k + '0');
        }
        if (tk) break;
      }
      if (tk) break;
    }
    if (tk && ans[0] != '0')
      cout << ans << '\n';
    else {
      for (int i = 0; i < s.length() - 2; i++) cout << "9";
      cout << '\n';
    }
  }
}
