#include <bits/stdc++.h>
using namespace std;
long long t, mask[200005], n;
string s;
bool fou;
int main() {
  ios_base::sync_with_stdio(false);
  long long precision = numeric_limits<long double>::digits10;
  cin >> t;
  for (long long qq = 1; qq <= t; qq++) {
    fou = false;
    cin >> s;
    n = (long long)s.size();
    s = "0" + s;
    for (long long i = 1; i <= n; i++) {
      mask[i] = mask[i - 1] ^ (1 << (s[i] - '0'));
    }
    for (long long i = n; i >= 1; i--) {
      if (fou) break;
      long long temp = s[i] - '0', c = 0;
      if (i == 1) c = 1;
      for (long long j = temp - 1; j >= c; j--) {
        if (fou) break;
        long long newMask = mask[i - 1] ^ (1 << j);
        vector<long long> st;
        for (long long k = 0; k <= 9; k++) {
          if ((newMask & (1 << k)) != 0) st.push_back(k);
        }
        long long rem = n - i;
        if (rem >= (long long)st.size()) {
          for (long long k = 1; k <= i - 1; k++) cout << s[k];
          cout << j;
          for (long long k = 1; k <= rem - (long long)st.size(); k++) cout << 9;
          for (long long k = (long long)st.size() - 1; k >= 0; k--)
            cout << st[k];
          cout << endl;
          fou = true;
          break;
        }
      }
    }
    if (fou) continue;
    for (long long i = 1; i <= n - 2; i++) cout << 9;
    cout << "\n";
  }
}
