#include <bits/stdc++.h>
using namespace std;
string str;
int odd[200001][10];
bool can(int in) {
  vector<int> miss;
  for (int i = 0; i < 10; i++) {
    if (odd[in][i]) miss.push_back(i);
  }
  if (miss.size() == 0) {
    if (in == (int)str.size() - 1) {
      cout << str;
      return 1;
    } else {
      if (str[in + 1] == '0')
        return 0;
      else {
        cout << str.substr(0, in + 1);
        cout << (char)(str[in + 1] - 1);
        for (int i = in + 2; i < (int)str.size() - 1; i++) {
          cout << 9;
        }
        cout << (char)(str[in + 1] - 1);
        return true;
      }
    }
  } else {
    if (in == (int)str.size() - 1 ||
        (int)str.size() - in - 1 < (int)miss.size() || str[in + 1] == '0' ||
        (str[in + 1] - '0' <= miss[0] &&
         (int)str.size() - in - 1 - 2 < (int)miss.size()))
      return false;
    cout << str.substr(0, in + 1);
    int mx = 10;
    for (auto el : miss)
      if (str[in + 1] - '0' > el) mx = el;
    bool xx = 0;
    if (mx != str[in + 1] - '0' - 1 &&
        (int)str.size() - in - 1 - 2 >= (int)miss.size()) {
      mx = str[in + 1] - '0' - 1;
      miss.push_back(mx);
      sort(miss.begin(), miss.end());
      in++;
      xx = 1;
    }
    cout << char(mx + '0');
    for (int j = 0; j < (int)str.size() - in - (int)miss.size() - 1; j++)
      cout << 9;
    for (auto it = miss.rbegin(); it != miss.rend(); it++) {
      if (!xx && *it == mx) continue;
      cout << *it;
    }
    return true;
  }
}
void alt() {
  if (str[0] == '1')
    for (int i = 0; i < (int)str.size() - 2; i++) cout << 9;
  else {
    cout << char(str[0] - 1);
    for (int i = 0; i < (int)str.size() - 2; i++) cout << '9';
    cout << char(str[0] - 1);
  }
}
bool solve() {
  int n = str.size();
  for (int j = 0; j < 10; j++) odd[0][j] = 0;
  odd[0][str[0] - '0'] = 1;
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < 10; j++) odd[i][j] = odd[i - 1][j];
    odd[i][str[i] - '0'] ^= 1;
  }
  for (int i = n - 1; i >= 0; i--) {
    if (can(i)) {
      return 1;
    }
  }
  return 0;
}
bool sub_one() {
  int i = (int)str.size() - 1;
  while (str[i--] == '0') str[i + 1] = '9';
  i++;
  if (i != 0 || str[i] != '1')
    str[i]--;
  else {
    for (int i = 0; i < (int)str.size() - 2; i++) {
      cout << 9;
    }
    cout << endl;
    return 1;
  }
  return 0;
}
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> str;
    if (sub_one()) continue;
    if (!solve()) alt();
    cout << endl;
  }
}
