#include <bits/stdc++.h>
using namespace std;
int mod = 1e9 + 7;
long long mod1 = 1e9 + 7;
const int maxL = 22;
const int maxn = 2e5;
const int baze = 330;
int ar[100];
string s;
int n;
bool solv(int pos, int ok, int mask) {
  int cnt = __builtin_popcount(mask);
  if (n - pos < cnt) return 0;
  if (pos == n) return 1;
  if (ok)
    if (n - pos == cnt) {
      for (int i = 9; i >= 0; i--)
        if ((mask >> i) & 1) s[pos] = '0' + i, pos++;
      return 1;
    } else {
      s[pos] = '9';
      return solv(pos + 1, ok, mask ^ ar[9]);
    }
  int x = s[pos] - '0';
  bool b = solv(pos + 1, 0, mask ^ ar[x]);
  if (b) return 1;
  for (x--; x >= 0; x--) {
    bool b = solv(pos + 1, 1, mask ^ ar[x]);
    if (b) {
      s[pos] = '0' + x;
      return 1;
    }
  }
  return 0;
}
void mns() {
  for (int i = n - 1; i >= 0; i--)
    if (s[i] == '0')
      s[i] = '9';
    else {
      s[i]--;
      break;
    }
  if (s[0] != '0') return;
  n -= 2;
  for (int i = 0; i < n; i++) s[i] = '9';
  s.resize(n);
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int t;
  for (int i = 0; i < 20; i++) ar[i] = (1LL << i);
  cin >> t;
  while (t--) {
    cin >> s;
    n = ((int)((s).size()));
    mns();
    solv(0, 0, 0);
    if (s[0] == '0')
      for (int i = 0; i < n - 2; i++) cout << 9;
    else
      cout << s;
    cout << '\n';
  }
}
