#include <bits/stdc++.h>
using namespace std;
const int N = (int)2e5 + 10;
int T, n;
char num[N];
int cnt[N][10];
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%s", num + 1);
    n = strlen(num + 1);
    for (int i = 0; i < 10; i++) cnt[0][i] = 0;
    for (int i = 1; i <= n; i++)
      for (int j = 0; j < 10; j++)
        cnt[i][j] = cnt[i - 1][j] + (num[i] == j + '0');
    bool find = false;
    for (int i = n; i >= 1 && !find; i--) {
      int _m = 0;
      for (int j = 0; j < 10; j++)
        if (cnt[i - 1][j] % 2 == 1) _m++;
      for (int k = num[i] - '0' - 1; k >= (i == 1 ? 1 : 0); k--) {
        int m = _m;
        if (cnt[i - 1][k] % 2 == 1)
          m--;
        else
          m++;
        if (n - i >= m) {
          find = true;
          for (int l = 1; l <= i - 1; l++) putchar(num[l]);
          printf("%d", k);
          for (int l = 1; l <= n - i - m; l++) putchar('9');
          for (int l = 9; l >= 0; l--)
            if (cnt[i - 1][l] % 2 == 1 && l != k)
              printf("%d", l);
            else if (cnt[i - 1][l] % 2 == 0 && l == k)
              printf("%d", l);
          puts("");
          break;
        }
      }
    }
    if (!find) {
      for (int i = 1; i <= n - 2; i++) putchar('9');
      puts("");
    }
  }
  return 0;
}
