#include <bits/stdc++.h>
using namespace std;
int const N = 200000;
char s[N + 1];
bool need[10];
int n;
inline int gtn() {
  int an = 9;
  while (!need[an]) --an;
  return an;
}
bool go(int i = 0, int ne = 0, bool fr = false) {
  if (i == n && ne == 0) return fr;
  int lft = n - i;
  char t = s[i];
  if (fr) {
    if (ne > lft) return false;
    if (ne < lft) {
      s[i] = '9';
      if (need[9])
        --ne, need[9] = false;
      else
        ++ne, need[9] = true;
      go(i + 1, ne, true);
      return true;
    } else {
      int z = gtn();
      s[i] = z + '0';
      need[z] = false;
      go(i + 1, ne - 1, true);
      return true;
    }
  }
  for (int j = s[i] - '0'; j >= (i == 0); --j) {
    int nne = ne;
    char z = j + '0';
    if (need[j])
      --nne, need[j] = false;
    else
      ++nne, need[j] = true;
    s[i] = z;
    if (go(i + 1, nne, z < t)) return true;
    s[i] = t;
    need[j] ^= 1;
  }
  return false;
}
void gr(int n) {
  for (int i = 0; i < (int)(n); ++i) s[i] = '9';
  s[n] = 0;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%s", s);
    n = strlen(s);
    if (!(n & 1) && go())
      printf("%s\n", s);
    else {
      --n;
      n >>= 1;
      n <<= 1;
      gr(n);
      printf("%s\n", s);
    }
  }
}
