#include <bits/stdc++.h>
using namespace std;
long long t[2 * 100005];
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int n;
  string s, ans;
  int test;
  cin >> test;
  while (test--) {
    cin >> s;
    n = s.length();
    t[0] = 0;
    for (int i = 1; i <= n; ++i) t[i] = t[i - 1] + s[i - 1] - '0';
    ans = "";
    bool can = true, less = false;
    int m = 0;
    for (int i = 0; i < n; ++i) {
      int l = ans.length();
      string f = "";
      for (int j = 0; j <= 9; ++j)
        if (m & 1 << j) f += j + '0';
      if (less) {
        m = 0;
        sort(f.begin(), f.end());
        reverse(f.begin(), f.end());
        l = n - i - f.length();
        while (l--) ans += "9";
        for (auto j : f) ans += j;
        break;
      } else {
        for (char j = s[i]; j >= '0' + (i == 0); --j) {
          auto cp = f;
          if (m & 1 << (j - '0'))
            f.erase(f.find(j), 1);
          else
            f += j;
          sort(f.begin(), f.end());
          int fl = f.length();
          if (i + fl <= n) {
            if (n - i - 1 > fl && t[n - fl] - t[i + 1] > 0) {
              if (j < s[i]) less = true;
              ans += j;
              m ^= 1 << (j - '0');
              break;
            } else if (j < s[i] || f < s.substr(n - fl, fl)) {
              if (j < s[i]) less = true;
              ans += j;
              m ^= 1 << (j - '0');
              break;
            } else if (f == s.substr(n - fl, fl) && j < s[i]) {
              less = true;
              ans += j;
              m ^= 1 << (j - '0');
              break;
            }
          }
          f = cp;
        }
      }
      if (ans.length() == l) {
        can = false;
        break;
      }
    }
    if (!can) {
      m = 0;
      n -= 2;
      ans = "";
      for (int i = 0; i < n; ++i) ans += "9";
    }
    assert(m == 0);
    cout << ans << "\n";
  }
  return 0;
}
