#include <bits/stdc++.h>
using namespace std;
long long int power(long long int a, long long int n) {
  long long int p = 1;
  while (n > 0) {
    if (n & 1) {
      p = ((p % 1000000007) * (a % 1000000007)) % 1000000007;
    }
    n >>= 1;
    a = ((a % 1000000007) * (a % 1000000007)) % 1000000007;
  }
  return p % 1000000007;
}
int inf = 10000000;
const long long B = 100000007;
const long long C = 10010107;
const int N = 500001;
int cn[26];
int main() {
  int test_case;
  cin >> test_case;
  while (test_case--) {
    long long int mask = 0;
    string st;
    cin >> st;
    for (int i = 0; i < st.length(); i++) {
      cn[st[i] - '0']++;
      mask ^= (1 << (st[i] - '0'));
    }
    int n = (int)st.length();
    for (int i = n - 1; i >= 0; i--) {
      mask ^= (1 << (st[i] - '0'));
      int j;
      for (j = (st[i] - '0') - 1; j >= 0; j--) {
        long long int nmask = (mask ^ (1 << j));
        if (__builtin_popcount(nmask) > n - 1 - i) continue;
        int l = n - 1;
        for (int dig = 0; dig <= 9; dig++) {
          if ((nmask >> dig) & 1) {
            st[l] = dig + '0';
            l--;
          }
        }
        while (l > i) {
          st[l] = '9';
          l--;
        }
        st[i] = j + '0';
        break;
      }
      if (j >= 0) break;
    }
    int i = 0;
    while (st[i] == '0') i++;
    int l = st.length();
    string ans = "";
    for (int id = i; id < l - ((l - i) % 2); id++) ans += st[id];
    cout << ans << endl;
  }
}
