#include <bits/stdc++.h>
using namespace std;
const long long N = 100005;
long long inf = 1e16;
long long mod = 1e9 + 7;
char en = '\n';
long long abs1(long long x) {
  if (x < 0) return 0;
  return x;
}
long long power(long long x, long long n, long long mod) {
  long long res = 1;
  x %= mod;
  while (n) {
    if (n & 1) res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
}
bool valid(long long check) { return check >= 0 && check % 2 == 0; }
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    long long n = s.length();
    long long arr[n + 5];
    long long pre[n + 5][12];
    for (long long i = 1; i <= n; i++) arr[i] = s[i - 1] - '0';
    memset(pre, 0, sizeof(pre));
    for (long long i = 1; i <= n; i++) {
      for (long long j = 0; j < 10; j++) pre[i][j] = pre[i - 1][j];
      pre[i][arr[i]] ^= 1;
    }
    long long flag = 0;
    for (long long i = n; i >= 1; i--) {
      long long st = (i == 1) ? 1 : 0;
      for (long long j = arr[i] - 1; j >= st; j--) {
        vector<long long> curr;
        long long freq[10];
        memset(freq, 0, sizeof(freq));
        for (long long k = 0; k < 10; k++) freq[k] = pre[i - 1][k];
        freq[j] ^= 1;
        for (long long k = 0; k < 10; k++) {
          if (freq[k]) curr.push_back(k);
        }
        long long rem = n - i;
        long long check = rem - curr.size();
        if (!valid(check)) {
          continue;
        }
        while (check--) curr.push_back(9);
        sort(curr.begin(), curr.end(), greater<long long>());
        for (long long k = 1; k < i; k++) cout << arr[k];
        cout << j;
        for (long long x : curr) cout << x;
        cout << en;
        flag = 1;
        break;
      }
      if (flag) break;
    }
    if (flag == 0) {
      n -= 2;
      while (n--) cout << 9;
      cout << en;
    }
  }
  return 0;
}
