#include <bits/stdc++.h>
using namespace std;
int arr[200005];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int cnt[10];
    int n = s.length();
    bool fl = 1;
    for (int i = 0; i < 10; i++) cnt[i] = 0;
    for (int i = 0; i < n; i++) arr[i] = s[i] - '0';
    for (int i = 0; i < n; i++) cnt[arr[i]]++;
    for (int i = n - 1; i >= 0 && fl; i--) {
      cnt[arr[i]]--;
      for (int j = arr[i] - 1; j >= 0 && fl; j--) {
        cnt[j]++;
        if (i == 0 && j == 0) {
          n--;
          if (n % 2 != 0) n--;
          for (int k = 0; k < n; k++) cout << "9";
          cout << endl;
          fl = 0;
          break;
        }
        vector<int> v;
        for (int k = 0; k < 10; k++)
          if (cnt[k] % 2 != 0) v.push_back(k);
        int lef = n - i - 1;
        if (lef >= v.size() && (lef - v.size()) % 2 == 0) {
          for (int k = 0; k < i; k++) cout << arr[k];
          cout << j;
          for (int k = (lef - v.size()) / 2; k > 0; k--) cout << "99";
          sort(v.begin(), v.end());
          for (int k = (int)v.size() - 1; k >= 0; k--) cout << v[k];
          cout << endl;
          fl = 0;
          break;
        }
        cnt[j]--;
      }
    }
  }
}
