#include <bits/stdc++.h>
using namespace std;
void doRoutine() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
void minus1(string &s) {
  long long i = (long long)s.size() - 1;
  while (i >= 0 && s[i] == '0') {
    s[i] = '9';
    --i;
  }
  --s[i];
  if (i == 0 && s[i] == '0') {
    s.erase(s.begin());
  }
}
void solve_ez(string &s) {
  long long n = s.size();
  string t(n - 2, '9');
  cout << t << endl;
}
void solve(string &s) {
  if (s.size() % 2 == 1) {
    cout << string((long long)s.size() - 1, '9') << endl;
    return;
  }
  long long n = s.size();
  vector<long long> pref(n + 1);
  for (long long i = 0; i < n; ++i) {
    pref[i + 1] = pref[i] + (s[i] - '0');
  }
  vector<long long> odd(10);
  long long max_pref = 0;
  for (long long i = 0; i < n; ++i) {
    long long dig = s[i] - '0';
    odd[dig] = (odd[dig] + 1) % 2;
    vector<long long> odds;
    for (long long c = 0; c < 10; ++c) {
      if (odd[c]) {
        odds.push_back(c);
      }
    }
    bool ok = false;
    long long cnt = odds.size();
    if (n - i - 1 >= cnt) {
      if (pref[n - cnt] - pref[i + 1] > 0) {
        ok = true;
      } else {
        ok = true;
        for (long long j = 0; j < cnt; ++j) {
          long long s_dig = (s[n - cnt + j] - '0');
          long long cur_dig = odds[j];
          if (cur_dig < s_dig) {
            break;
          } else if (cur_dig > s_dig) {
            ok = false;
          }
        }
      }
    }
    if (!ok) {
      break;
    } else {
      max_pref = i + 1;
    }
  }
  if (max_pref == n) {
    cout << s << endl;
    return;
  }
  for (long long c = (s[max_pref] - '0') - 1; c >= (max_pref == 0 ? 1 : 0);
       --c) {
    fill(odd.begin(), odd.end(), 0);
    for (long long i = 0; i < max_pref; ++i) {
      long long dig = s[i] - '0';
      odd[dig] = (odd[dig] + 1) % 2;
    }
    odd[c] = (odd[c] + 1) % 2;
    vector<long long> odds;
    for (long long x = 9; x >= 0; --x) {
      if (odd[x]) {
        odds.push_back(x);
      }
    }
    if ((long long)odds.size() <= n - max_pref - 1) {
      string res;
      for (long long i = 0; i < max_pref; ++i) {
        res.push_back(s[i]);
      }
      res.push_back((char)(c + '0'));
      for (long long i = 0; i < n - max_pref - 1 - (long long)odds.size();
           ++i) {
        res.push_back('9');
      }
      for (auto el : odds) {
        res.push_back((char)(el + '0'));
      }
      cout << res << endl;
      return;
    }
  }
  solve_ez(s);
}
signed main() {
  doRoutine();
  long long n;
  cin >> n;
  while (n--) {
    string s;
    cin >> s;
    minus1(s);
    solve(s);
  }
  return 0;
}
