#include <bits/stdc++.h>
using namespace std;
int T, len;
string number;
int a[10];
bool work(int i) {
  a[number[i] - '0']--;
  if (number[i] == '0') {
    return (false);
  }
  int b[10];
  for (char t = number[i] - 1; t >= '0'; t--) {
    a[t - '0']++;
    memset(b, 0, sizeof(b));
    for (int x = 0; x <= 9; x++) {
      if (a[x] % 2) {
        b[x] = 1;
      }
    }
    int tot = 0;
    for (int x = 0; x <= 9; x++) {
      tot += b[x];
    }
    if (len - 1 - i >= tot) {
      number[i] = t;
      for (int j = i + 1; j <= len - tot - 1; j++) number[j] = '9';
      int cnt = 9;
      while (b[cnt] == 0) {
        cnt--;
      }
      for (int j = len - tot; j <= len - 1; j++) {
        number[j] = cnt + '0';
        cnt--;
        while (b[cnt] == 0 && cnt >= 0) {
          cnt--;
        }
      }
      return (true);
    }
    a[t - '0']--;
  }
  return (false);
}
int main() {
  cin >> T;
  for (int i = 1; i <= T; i++) {
    cin >> number;
    memset(a, 0, sizeof(a));
    len = number.length();
    for (int i = 0; i <= len - 1; i++) a[number[i] - '0']++;
    int cur = len - 1;
    while (!work(cur)) {
      cur--;
    }
    if (cur != 0 || number[0] != '0') {
      cout << number << endl;
    } else {
      for (int j = 1; j <= len - 2; j++) {
        cout << "9";
      }
      cout << endl;
    }
  }
}
