#include <bits/stdc++.h>
char s[(200010)];
int n1[1 << 11];
void init() {
  for (int i = 1; i < 1024; ++i) {
    for (int j = 0; j < 10; ++j) {
      n1[i] += !!((1 << j) & i);
    }
  }
}
int main() {
  init();
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", s);
    int ten = s[0] == '1';
    int n = strlen(s);
    for (int i = 1; i < n - 1; ++i) {
      if (s[i] != '0') {
        ten = 0;
        break;
      }
    }
    ten &= s[n - 1] == '1' || s[n - 1] == '0';
    if (ten) {
      for (int i = 0; i < n - 2; ++i) {
        printf("9");
      }
      printf("\n");
      continue;
    }
    int msk = 0;
    for (int i = 0; i < n; ++i) {
      msk ^= 1 << s[i] - '0';
    }
    int findans = 0;
    for (int i = n - 1; ~i && !findans; --i) {
      msk ^= 1 << s[i] - '0';
      for (int j = s[i] - '0' - 1; ~j && !findans; --j) {
        msk ^= 1 << j;
        if (n1[msk] <= n - i - 1) {
          findans = 1;
          s[i] = j + '0';
          int k = n - 1;
          for (int l = 0; l < 10; ++l) {
            if (msk & (1 << l)) {
              s[k] = l + '0';
              k--;
            }
          }
          for (; k > i; --k) {
            s[k] = '9';
          }
        }
        msk ^= 1 << j;
      }
    }
    printf("%s\n", s);
  }
}
