#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 7;
const int MAXNUM = 1 << 10;
int T;
string S[100007];
void Input() {
  cin >> T;
  for (int i = 1; i <= T; i++) cin >> S[i];
}
int memo[MAXN][MAXNUM];
int trace[MAXN][MAXNUM];
int solve(int i, int mask) {
  if (i == 0) return !mask;
  if (memo[i][mask] != -1) return memo[i][mask];
  for (int j = 9; j >= 0; j--)
    if (solve(i - 1, mask ^ (1 << j))) {
      trace[i][mask] = j;
      return memo[i][mask] = 1;
    }
  return memo[i][mask] = 0;
}
bool Result(const string &s) {
  int len = (int)s.size() - 1;
  int mask = 0;
  for (int i = 0; i <= len; i++) mask ^= (1 << (s[i] - '0'));
  for (int i = len; i >= 0; i--) {
    int temp = s[i] - '0';
    mask ^= (1 << temp);
    int lim = (i == 0) ? 1 : 0;
    for (int j = temp - 1; j >= lim; j--)
      if (solve(len - i, mask ^ (1 << j))) {
        for (int k = 0; k < i; k++) cout << s[k];
        cout << char(j + '0');
        mask ^= (1 << j);
        int k = len - i;
        while (k) {
          temp = trace[k][mask];
          cout << char(temp + '0');
          mask ^= (1 << temp);
          k--;
        }
        cout << '\n';
        return 1;
      }
  }
  return 0;
}
void Output() {
  memset(memo, -1, sizeof memo);
  for (int i = 1; i <= T; i++) {
    if (Result(S[i]) == 0) {
      for (int j = 0; j < (int)S[i].size() - 2; j++) cout << 9;
      cout << '\n';
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  Input();
  Output();
  return 0;
}
