#include <bits/stdc++.h>
using namespace std;
int T;
string s;
bool cnt[200005][10];
string ans;
string a[11];
bool flag;
int main() {
  a[0] = "";
  for (int i = 1; i <= 10; i++) a[i] = a[i - 1] + '9';
  cin >> T;
  while (T--) {
    cin >> s;
    s = '0' + s;
    int x;
    for (int i = 1; i < s.size(); i++) {
      x = s[i] - '0';
      for (int j = 0; j <= 9; j++) cnt[i][j] = cnt[i - 1][j] ^ (j == x);
    }
    int res;
    ans = "";
    flag = false;
    for (int i = s.size() - 1; i >= 1; i--) {
      for (int j = s[i] - '0' - 1; j >= 0; j--) {
        if (i == 1 && j == 0) break;
        res = 0;
        for (int k = 0; k <= 9; k++)
          if (cnt[i - 1][k] ^ (j == k)) res++;
        if (res <= s.size() - i - 1) {
          if (i != 1) ans = s.substr(1, i - 1);
          ans += j + '0';
          ans += a[s.size() - i - 1 - res];
          for (int k = 9; k >= 0; k--)
            if (cnt[i - 1][k] ^ (j == k)) ans += k + '0';
          flag = true;
          break;
        }
      }
      if (flag) break;
    }
    if (flag)
      cout << ans << endl;
    else {
      for (int i = 1; i < s.size() - 2; i++) cout << '9';
      cout << endl;
    }
  }
  return 0;
}
