#include <bits/stdc++.h>
using namespace std;
int n;
string s, ans;
set<long long> mk;
bool f(int p, bool less, int m) {
  if (mk.find((p << 11) + (m << 1) + less) != mk.end()) return false;
  if (p == n) return less && m == 0;
  mk.insert((p << 11) + (m << 1) + less);
  for (char i = '9', to = '0' + (p == 0); i >= to; --i) {
    ans[p] = i;
    if (less) {
      if (f(p + 1, less, m ^ 1 << (i - '0'))) return true;
    } else {
      if (i == s[p] && f(p + 1, less, m ^ 1 << (i - '0')))
        return true;
      else if (i < s[p] && f(p + 1, true, m ^ 1 << (i - '0')))
        return true;
    }
  }
  return false;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int t = 1;
  cin >> t;
  while (t--) {
    cin >> s;
    ans = s;
    n = s.length();
    mk.clear();
    if (!f(0, 0, 0)) {
      n -= 2;
      ans = "";
      for (int i = 0; i < n; ++i) ans += "9";
    }
    cout << ans << "\n";
  }
  return 0;
}
