#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long powmod(long long a, long long b, long long MOD) {
  if (a == 0ll) {
    return 0ll;
  }
  a %= MOD;
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = ans * a % MOD;
    }
    a = a * a % MOD;
    b >>= 1;
  }
  return ans;
}
long long poww(long long a, long long b) {
  if (a == 0ll) {
    return 0ll;
  }
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = ans * a;
    }
    a = a * a;
    b >>= 1;
  }
  return ans;
}
void Pv(const vector<int> &V) {
  int Len = int(V.size());
  for (int i = 0; i < Len; ++i) {
    printf("%d", V[i]);
    if (i != Len - 1) {
      printf(" ");
    } else {
      printf("\n");
    }
  }
}
void Pvl(const vector<long long> &V) {
  int Len = int(V.size());
  for (int i = 0; i < Len; ++i) {
    printf("%lld", V[i]);
    if (i != Len - 1) {
      printf(" ");
    } else {
      printf("\n");
    }
  }
}
inline long long readll() {
  long long tmp = 0, fh = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') fh = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar();
  return tmp * fh;
}
inline int readint() {
  int tmp = 0, fh = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') fh = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar();
  return tmp * fh;
}
void pvarr_int(int *arr, int n, int strat = 1) {
  if (strat == 0) {
    n--;
  }
  for (int i = strat; i <= n; i++) {
    printf("%d%c", arr[i], i == n ? '\n' : ' ');
  }
}
void pvarr_LL(long long *arr, int n, int strat = 1) {
  if (strat == 0) {
    n--;
  }
  for (int i = strat; i <= n; i++) {
    printf("%lld%c", arr[i], i == n ? '\n' : ' ');
  }
}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
char s[maxn];
int n;
bool solve(int id, int info, int last, int eq) {
  if (!eq) {
    if (id + __builtin_popcount(info) <= n) {
      for (int i = 0; i <= id - 2; i++) {
        printf("%c", s[i]);
      }
      printf("%d", last);
      int rm = n - id - __builtin_popcount(info);
      while (rm--) {
        printf("9");
      }
      for (int i = 9; i >= 0; --i) {
        if ((1 << i) & info) {
          printf("%d", i);
        }
      }
      printf("\n");
      return 1;
    }
    return 0;
  }
  for (int i = s[id] - '0'; i >= 0 + (!id); --i) {
    if (solve(id + 1, info ^ (1 << i), i, eq & (i == s[id] - '0'))) {
      return 1;
    }
  }
  return 0;
}
int main() {
  int t;
  t = readint();
  while (t--) {
    scanf("%s", s);
    n = strlen(s);
    if (!solve(0, 0, -1, 1)) {
      for (int i = 1; i <= n - 2; i++) {
        printf("9");
      }
      printf("\n");
    }
  }
  return 0;
}
