#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int t;
char a[N];
int ch(int f[]) {
  int ct = 0;
  for (int i = 0; i < 10; i++) ct += f[i] & 1;
  return ct;
}
int find(int f[]) {
  for (int i = 9; i >= 0; i--)
    if (f[i] & 1) return i;
  return -1;
}
int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%s", a);
    string s = a;
    int v = 0;
    int f[10] = {0};
    for (int i = 0; i < s.size(); i++) f[s[i] - '0']++;
    int y = 0;
    for (int i = s.size() - 1; i >= 0; i--) {
      int c = s[i] - '0';
      f[c]--;
      int no = (c == 1) && !i;
      if (no) {
        for (int i = 0; i < s.size() - 2; i++) printf("9");
        puts("");
        break;
      }
      for (int j = c - 1; j > -1; j--) {
        f[j]++;
        int g = ch(f);
        if (g <= v) {
          s[i] = j + '0';
          i++;
          for (int j = i; j < (int)s.size() - g; j++) {
            s[j] = '9';
          }
          i = s.size() - g;
          while (i < s.size()) {
            int m = find(f);
            if (m == -1) break;
            s[i++] = m + '0';
            f[m]++;
          }
          for (int i = 0; i < s.size(); i++) {
            if (s[i] != '0') {
              for (int j = i; j < s.size(); j++) printf("%c", s[j]);
              puts("");
              y = 1;
              break;
            }
          }
          y = 1;
          break;
        }
        f[j]--;
      }
      v++;
      if (y) break;
    }
  }
}
