#include <bits/stdc++.h>
using namespace std;
int in() {
  int x, y;
  y = scanf("%d", &x);
  return x;
}
int cnt[10];
int a[200 * 1000 + 5];
int main() {
  int t = in();
  while (t--) {
    string s;
    cin >> s;
    int n = s.length();
    for (int i = 0; i < 10; i++) cnt[i] = 0;
    for (int i = 0; i < n; i++) {
      a[i] = (s[i] - '0');
      cnt[a[i]]++;
    }
    bool found = false;
    for (int i = n - 1; i >= 0 && !found; i--) {
      cnt[a[i]]--;
      for (int j = a[i] - 1; j >= 0 && !found; j--) {
        if (i == 0 && j == 0) continue;
        cnt[j]++;
        int odd = 0;
        for (int d = 0; d < 10; d++) odd += cnt[d] % 2;
        if (odd <= n - i - 1) {
          for (int ii = 0; ii < i; ii++) cout << a[ii];
          cout << j;
          for (int ii = 0; ii < (n - i - 1) - odd; ii++) cout << 9;
          for (int ii = 9; ii >= 0; ii--)
            if (cnt[ii] % 2) cout << ii;
          cout << '\n';
          found = true;
        }
        cnt[j]--;
      }
    }
    if (!found) {
      for (int i = 0; i < n - 2; i++) cout << 9;
      cout << '\n';
    }
  }
  return 0;
}
