#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int MOD = 1e9 + 7;
int prefixMask[maxn];
bool check(int len, int mask, string& res) {
  int k = 0;
  for (int i = 0; i < 10; i++) {
    if (mask & (1 << i)) k++;
  }
  if (k > len || (len - k) % 2 == 1) return false;
  res = "";
  for (int i = 0; i < len - k; i++) res += '9';
  for (int i = 9; i >= 0; i--) {
    if (mask & (1 << i)) res += (i + '0');
  }
  return true;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string str, temp;
    cin >> str;
    int n = str.size();
    temp = '1';
    for (int i = 1; i < n - 1; i++) temp += '0';
    temp += '1';
    if (str == temp || str < temp) {
      temp = "";
      for (int i = 2; i < n; i++) temp += '9';
      cout << temp << endl;
      continue;
    }
    int mask = 0;
    for (int i = 0; i < n; i++) {
      mask ^= (1 << (str[i] - '0'));
      prefixMask[i] = mask;
    }
    for (int i = n - 1; i >= 0; i--) {
      bool chk = false;
      for (int j = str[i] - '0' - 1; j >= 0; j--) {
        mask = i > 0 ? prefixMask[i - 1] : 0;
        mask ^= (1 << j);
        if (check(n - 1 - i, mask, temp)) {
          string res = str.substr(0, i);
          res += (j + '0');
          res += temp;
          cout << res << endl;
          chk = true;
          break;
        }
      }
      if (chk) break;
    }
  }
  return 0;
}
