#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6 + 5;
int mask;
char a[MAX];
int main() {
  int cas;
  scanf("%d", &cas);
  while (cas--) {
    scanf("%s", a);
    int l = strlen(a);
    mask = 0;
    for (int i = 0; i < l; i++) {
      mask ^= (1 << (a[i] - '0'));
    }
    l--;
    bool ok = false;
    for (int i = l; i >= 0 && !ok; i--) {
      mask ^= (1 << (a[i] - '0'));
      if (a[i] == '0' || (a[i] == '1' && i == 0)) continue;
      for (int j = a[i] - '0' - 1; j >= 0 && !ok; j--) {
        int nmask = mask ^ (1 << j);
        int c = __builtin_popcount(nmask);
        if (l - i < c) continue;
        a[i] = '0' + j;
        int bit = 10;
        for (int k = i + 1; k <= l; k++) {
          if (k - i <= l - i - c)
            a[k] = '9';
          else {
            while (!(nmask & (1 << bit))) bit--;
            a[k] = '0' + bit;
            bit--;
          }
        }
        ok = true;
      }
    }
    if (ok)
      printf("%s", a);
    else
      while (l > 1) {
        printf("9");
        l--;
      }
    printf("\n");
  }
  return 0;
}
