#include <bits/stdc++.h>
using namespace std;
const int MAX = 200000 + 10;
char s[MAX];
map<int, int> mp;
vector<int> v;
int len;
bool judge() {
  for (int i = len - 1; i >= 0; --i) {
    int t;
    if (i == 0)
      t = 1;
    else
      t = 0;
    --mp[s[i] - '0'];
    for (int j = s[i] - '0' - 1; j >= t; --j) {
      ++mp[j];
      v.clear();
      for (int k = 0; k < 10; ++k) {
        if (mp[k] & 1) {
          v.push_back(k);
        }
      }
      int l = v.size();
      if (l <= len - i - 1) {
        for (int k = 0; k < i; ++k) {
          printf("%c", s[k]);
        }
        printf("%d", j);
        for (int k = 0; k < len - i - 1 - l; ++k) {
          printf("9");
        }
        sort(v.begin(), v.end());
        for (int k = l - 1; k >= 0; --k) {
          printf("%d", v[k]);
        }
        printf("\n");
        return true;
      }
      --mp[j];
    }
  }
  return false;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    mp.clear();
    cin >> s;
    len = strlen(s);
    for (int i = 0; i < len; ++i) {
      ++mp[s[i] - '0'];
    }
    if (!judge()) {
      for (int i = 0; i < len - 2; ++i) {
        printf("9");
      }
      printf("\n");
    }
  }
  return 0;
}
