#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
char s[N];
int cnt[10];
void solve(int n) {
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < n; i++) {
    cnt[s[i] - '0']++;
  }
  for (int i = n - 1; i >= 0; i--) {
    cnt[s[i] - '0']--;
    int ini = i ? 0 : 1;
    for (int d = s[i] - '0' - 1; d >= ini; d--) {
      cnt[d]++;
      int odds = 0;
      for (int j = 0; j < 10; j++) odds += cnt[j] % 2;
      int lack = n - i - 1 - odds;
      if (lack >= 0 && lack % 2 == 0) {
        for (int j = 0; j < i; j++) printf("%c", s[j]);
        printf("%d", d);
        while (lack--) printf("9");
        for (int j = 9; j >= 0; j--)
          if (cnt[j] % 2 == 1) printf("%d", j);
        printf("\n");
        return;
      }
      cnt[d]--;
    }
  }
  for (int i = 2; i < n; i++) printf("9");
  printf("\n");
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%s", s);
    solve((int)strlen(s));
  }
  return 0;
}
