#include <bits/stdc++.h>
using namespace std;
void solve(string& s) {
  int last_index = -1;
  int target = -1;
  vector<int> target_set;
  bool seen[10];
  fill(seen, seen + 10, 0);
  for (int i = 0; i < s.size(); i++) {
    char start = s[i] - 1;
    char end = !i ? '1' : '0';
    while (start >= end) {
      bool sp[10];
      for (int j = 0; j < 10; j++) {
        sp[j] = seen[j];
      }
      sp[start - '0'] ^= 1;
      int t = 0;
      for (int j = 0; j < 10; j++) {
        if (sp[j]) t++;
      }
      int letter_rem = s.size() - i - 1;
      if (t <= letter_rem) {
        last_index = i;
        target_set.clear();
        for (int j = 9; j >= 0; j--) {
          if (sp[j]) target_set.push_back(j);
        }
        target = start - '0';
        break;
      }
      start--;
    }
    seen[s[i] - '0'] ^= 1;
  }
  if (last_index == -1) {
    int q = s.size() - 2;
    for (int i = 0; i < q; i++) {
      cout << '9';
    }
    cout << endl;
  } else {
    for (int i = 0; i < last_index; i++) {
      cout << s[i];
    }
    cout << target;
    int rem = s.size() - last_index - 1 - target_set.size();
    for (int i = 0; i < rem; i++) {
      cout << '9';
    }
    for (int i = 0; i < target_set.size(); i++) {
      cout << target_set[i];
    }
    cout << endl;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    solve(s);
  }
  return 0;
}
