#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T BM(T p, T e, T M) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T mul(T p, T e, T M) {
  long long int ret = 0;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret + p);
    p = (p + p);
    if (ret >= M) ret -= M;
    if (p >= M) p -= M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T mdINV(T a, T M) {
  return BM(a, M - 2, M);
}
template <class T>
inline T PW(T p, T e) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p);
    p = (p * p);
  }
  return (T)ret;
}
template <class T>
bool ISLEFT(T a, T b, T c) {
  if (((a.first.first - b.first.first) * (b.second.second - c.second.second) -
       (b.first.first - c.first.first) * (a.second.second - b.second.second)) <
      0.0)
    return 1;
  else
    return 0;
}
char a[2000007 + 2];
int ar[2000007 + 2];
int main() {
  int tc;
  scanf("%d", &tc);
  while (tc--) {
    scanf("%s", a + 1);
    int l = strlen(a + 1);
    ar[0] = 0;
    for (int i = 1; i <= l; i++) {
      int first = a[i] - '0';
      ar[i] = ar[i - 1];
      ar[i] ^= (1 << first);
    }
    bool fl = 0;
    for (int j = l; j >= 1; j--) {
      int hi = 0;
      if (j == 1) hi = 1;
      for (int i = a[j] - '0' - 1; i >= hi; i--) {
        int first = ar[j - 1];
        first ^= (1 << i);
        int ko = __builtin_popcount(first);
        if ((l - j) >= ko && (l - j - ko) % 2 == 0) {
          for (int k = 1; k <= j - 1; k++) printf("%c", a[k]);
          printf("%d", i);
          for (int k = 1; k <= l - j - ko; k++) printf("9");
          for (int k = 9; k >= 0; k--) {
            if ((first & (1 << k))) printf("%d", k);
          }
          printf("\n");
          fl = 1;
          break;
        }
      }
      if (fl) break;
    }
    if (!fl) {
      for (int i = 1; i <= l - 2; i++) printf("9");
      printf("\n");
    }
  }
  return 0;
}
