#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
void read(int &x) {
  char ch;
  bool flag = 0;
  for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1);
       ch = getchar())
    ;
  for (x = 0; isdigit(ch); x = (x << 1) + (x << 3) + ch - 48, ch = getchar())
    ;
  x *= 1 - 2 * flag;
}
void print(int x) {
  if (x > 9) print(x / 10);
  putchar(x % 10 + 48);
}
void write(int x) {
  if (x < 0) putchar('-');
  print(((x) < 0 ? (-(x)) : (x)));
}
char ch[N + 5];
int a[10], len;
void work() {
  scanf("%s", ch);
  len = strlen(ch);
  for (int i = 0; i < 10; i++) a[i] = 0;
  for (int i = 0; i < len; i++) ++a[ch[i] - '0'];
  for (int i = len - 1; i >= 0; i--) {
    --a[ch[i] - '0'];
    int beg = (i == 0);
    for (int k = ch[i] - '0' - 1; k >= beg; k--) {
      ++a[k];
      int t = 0;
      for (int j = 0; j < 10; j++)
        if (a[j] & 1) ++t;
      if (t > len - i - 1 || (len - i - 1 - t) % 2) {
        --a[k];
        continue;
      }
      for (int j = 0; j < i; j++) putchar(ch[j]);
      putchar('0' + k);
      for (int j = 1; j <= len - i - 1 - t; j++) putchar('9');
      for (int j = 9; j >= 0; j--)
        if (a[j] & 1) putchar('0' + j);
      return;
    }
  }
  for (int i = 0; i < len - 2; i++) putchar('9');
}
int main() {
  int t;
  read(t);
  while (t--) work(), putchar('\n');
  return 0;
}
