#include <bits/stdc++.h>
using namespace std;
int temp[10], cnt[10];
int check() {
  for (int i = 0; i < 10; i++)
    if (cnt[i] % 2 == 1) return 0;
  return 1;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    string str, ans;
    cin >> str;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < str.size(); i++) {
      int d = str[i] - '0';
      cnt[d]++;
    }
    for (int i = str.size() - 1; i >= 1; i--) {
      int now = str[i] - '0';
      for (int j = 0; j < 10; j++) temp[j] = cnt[j];
      temp[now]--;
      for (int j = now - 1; j >= 0; j--) {
        temp[j]++;
        int need = 0, rest = str.size() - i - 1;
        vector<int> save;
        for (int k = 0; k < 10; k++) {
          if (temp[k] % 2 == 1) {
            need++;
            save.push_back(k);
          }
        }
        temp[j]--;
        if (need > rest) continue;
        int baki = rest - need;
        if (baki % 2 == 1) continue;
        for (int l = 0; l < i; l++) {
          ans += str[l];
        }
        ans += char(j + '0');
        for (int l = 0; l < baki; l++) ans += "9";
        reverse(save.begin(), save.end());
        for (int l : save) ans += char(l + '0');
        goto here;
      }
      cnt[now]--;
    }
  here:
    if (ans.size() == 0) {
      if (str.size() % 2 == 1) {
        for (int j = 0; j < str.size() - 1; j++) ans += "9";
      } else {
        str[0]--;
        if (str[0] > '0') ans += str[0];
        for (int j = 1; j < str.size() - 1; j++) ans += "9";
        if (str[0] > '0') ans += str[0];
      }
    }
    cout << ans << "\n";
    continue;
  }
}
