#include <bits/stdc++.h>
using namespace std;
const int inf = 1.01e9;
const double eps = 1e-9;
const int N = 2e5 + 10;
char s[N];
int a[N];
int b[N];
int n;
int found;
void go(int pos, int mask, int f, int l) {
  if (__builtin_popcount(mask) + pos > n) return;
  if (found) return;
  if (pos == n) {
    if (l == 0) return;
    int fst = 0;
    for (int i = 0; (i) < (n); ++i) {
      if (b[i] > 0) fst = 1;
      if (fst) putchar('0' + b[i]);
    }
    assert(fst);
    puts("");
    found = 1;
    return;
  }
  for (int i = 9; i >= 0; --i)
    if (l || (i <= a[pos])) {
      b[pos] = i;
      if (f == 0 && (n - pos) % 2 == 1 && i > 0) continue;
      if (f == 0 && i == 0) {
        go(pos + 1, 0, 0, l | (b[pos] < a[pos]));
      } else {
        go(pos + 1, mask ^ (1LL << (i)), 1, l | (b[pos] < a[pos]));
      }
    }
}
int main() {
  int tn;
  scanf("%d", &tn);
  for (int tt = 0; (tt) < (tn); ++tt) {
    scanf("%s", s);
    fprintf(stderr, "%s\n", s), fflush(stderr);
    n = strlen(s);
    for (int i = 0; (i) < (n); ++i) a[i] = s[i] - '0';
    found = 0;
    go(0, 0, 0, 0);
  }
  return 0;
}
