#include <bits/stdc++.h>
using namespace std;
bool check(string s) {
  long long a = 0;
  for (long long i = 0; i < (long long)s.size(); i++) {
    if (s[i] != '0' and s[i] != '1') return false;
    a += s[i] == '1';
  }
  return (a == 1);
}
long long n;
string s;
void solv() {
  vector<bool> cnt(10, 0);
  cin >> s;
  n = s.size();
  if (check(s)) {
    for (long long i = 0; i < n - 2; i++) cout << '9';
    cout << '\n';
    return;
  }
  vector<long long> odd(n, 0);
  long long las = -69;
  for (long long i = 0; i < n; i++) {
    bool ok = 0;
    cnt[s[i] - '0'] = cnt[s[i] - '0'] ^ 1;
    if (cnt[s[i] - '0'])
      odd[i]++;
    else
      odd[i]--;
    if (i > 0) odd[i] += odd[i - 1];
    if (s[i] == '0') continue;
    bool les = 0;
    for (long long j = 0; j < s[i] - '0'; j++) les |= cnt[j];
    if (les and n - i >= (i ? odd[i - 1] : 0)) {
      ok = true;
    } else if (!les and n - i >= (i ? odd[i - 1] : 0) + 2) {
      ok = true;
    }
    if (ok) las = i;
  }
  assert(las != -69);
  if (las == 0) {
    if (s[0] != '1') cout << s[0] - '0' - 1;
    for (long long i = 0; i < n - 2; i++) cout << '9';
    if (s[0] != '1') cout << s[0] - '0' - 1;
    cout << '\n';
    return;
  }
  string ans = "";
  for (long long i = 0; i < las; i++) ans += s[i];
  vector<bool> req(10, 0);
  for (long long i = 0; i < las; i++) req[s[i] - '0'] = req[s[i] - '0'] ^ 1;
  long long reqcnt = 0;
  for (long long i = 0; i < 10; i++) reqcnt += req[i];
  bool done = 0;
  if (s[las] != '0')
    if (n - las >= 2 + reqcnt or req[s[las] - '0' - 1]) {
      done = 1;
      char c = s[las];
      c--;
      ans += c;
      req[c - '0'] = req[c - '0'] ^ 1;
      las++;
    }
  if (!done)
    for (long long i = s[las] - '0' - 1; i >= 0; i--) {
      if (req[i]) {
        char c = (char)'0' + i;
        ans += c;
        req[i] = 0;
        done = 1;
        las++;
        break;
      }
    }
  assert(done);
  reqcnt = 0;
  for (long long i = 0; i < 10; i++) reqcnt += req[i];
  long long d = n - las - reqcnt;
  for (long long i = 0; i < d; i++) ans += '9';
  for (long long i = 9; i >= 0; i--) {
    if (!req[i]) continue;
    char c = (char)'0' + i;
    ans += c;
  }
  cout << ans << '\n';
}
signed main() {
  long long t;
  cin >> t;
  while (t--) solv();
}
