#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int h[10] = {};
bool trySolve(int i) {
  int ex = s.size() - 1 - i, j, k;
  for (j = s[i] - '0' - 1; j >= 0; j--) {
    h[j + 1]--;
    h[j]++;
    s[i] = '0' + j;
    int numOdd = 0, numEven = 0, digits = 0;
    for (k = 0; k <= 9; k++) {
      digits += h[k];
      if (h[k] % 2 == 1)
        numOdd++;
      else
        numEven++;
    }
    if (ex == 0 && digits - h[0] == 1) {
    } else if (ex >= numOdd && !(i == 0 && s[i] == '0')) {
      vector<int> left;
      for (k = 0; k <= 9; k++) {
        if (h[k] % 2 == 1) left.push_back(k);
      }
      cout << s.substr(0, i + 1);
      for (k = numOdd; k < ex; k++) left.push_back(9);
      sort(left.begin(), left.end(), greater<int>());
      for (k = 0; k < left.size(); k++) cout << left[k];
      cout << '\n';
      return true;
    }
  }
  h[0]--;
  return false;
}
int main() {
  int i, z = 0;
  cin >> n;
  for (z = 0; z < n; z++) {
    cin >> s;
    for (i = 0; i < 10; i++) h[i] = 0;
    for (i = 0; i < s.size(); i++) h[(int)(s[i] - '0')]++;
    int solved = 0;
    if (s.size() % 2 == 0) {
      for (i = s.size() - 1; i >= 0; i--) {
        if (trySolve(i)) {
          solved = 1;
          break;
        }
      }
    }
    if (solved == 0) {
      int ns = s.size();
      if (ns % 2 == 1)
        ns--;
      else
        ns -= 2;
      for (i = 0; i < ns; i++) cout << 9;
      cout << '\n';
    }
  }
}
