#include <bits/stdc++.h>
using namespace std;
string s;
char c[200005];
int dem[11];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int Tests;
  cin >> Tests;
  while (Tests--) {
    cin >> s;
    int n = s.size();
    int pos = -1;
    int cpos = 0;
    memset(dem, 0, sizeof dem);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j + '0' < s[i]; j++) {
        if (i == 0 && j == 0) continue;
        int cnt = 0;
        dem[j] ^= 1;
        for (int k = 0; k <= 9; k++) cnt += dem[k];
        if (cnt + i + 1 <= n) {
          pos = i + 1;
          cpos = j;
        }
        dem[j] ^= 1;
      }
      dem[s[i] - '0'] ^= 1;
    }
    if (pos == -1) {
      for (int i = 1; i <= n - 2; i++) cout << 9;
      cout << '\n';
    } else {
      for (int i = 1; i <= n; i++) c[i] = '9';
      memset(dem, 0, sizeof dem);
      for (int i = 1; i < pos; i++) c[i] = s[i - 1], dem[c[i] - '0'] ^= 1;
      c[pos] = cpos + '0';
      dem[c[pos] - '0'] ^= 1;
      int cur = n;
      for (int i = 0; i <= 9; i++)
        if (dem[i]) c[cur--] = '0' + i;
      for (int i = 1; i <= n; i++) cout << c[i];
      cout << '\n';
    }
  }
}
