#include <bits/stdc++.h>
using namespace std;
int cnt[10];
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int q;
  cin >> q;
  while (q--) {
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < 10; i++) {
      cnt[i] = 0;
    }
    for (int i = 0; i < n; i++) {
      cnt[s[i] - '0'] ^= 1;
    }
    bool ok = 0;
    for (int i = n - 1; i >= 0; i--) {
      cnt[s[i] - '0'] ^= 1;
      for (int j = s[i] - '0' - 1; j >= 0; j--) {
        cnt[j] ^= 1;
        int num = 0;
        for (int k = 0; k < 10; k++) {
          if (cnt[k]) num++;
        }
        if (num <= (n - i - 1) && (n - i - num) % 2 == 1) {
          s[i] = (char)('0' + j);
          int ss = 0;
          for (int k = n - 1; k > i; k--) {
            if (ss >= 9)
              s[k] = (char)('0' + 9);
            else {
              while (!cnt[ss]) ss++;
              ss = min(ss, 9);
              s[k] = (char)('0' + ss);
              ss++;
            }
          }
          ok = 1;
        }
        if (ok) break;
        cnt[j] ^= 1;
      }
      if (ok) break;
    }
    if (s[0] == '0') {
      for (int j = 0; j < n - 2; j++) {
        cout << 9;
      }
      cout << endl;
    } else {
      cout << s << endl;
    }
  }
}
