#include <bits/stdc++.h>
using namespace std;
char s[200005];
int n;
char r[200005];
set<long long> v;
bool go(int k, int l, int m) {
  if (k == n) return l && !m;
  long long a = ((1LL * k) << 30) | (m << 1) | l;
  if (v.count(a)) return false;
  v.insert(a);
  if (l) {
    for (int i = 9; i >= 0; --i)
      if (go(k + 1, l, m ^ (1 << i))) {
        r[k] = '0' + i;
        return true;
      }
  } else {
    if (go(k + 1, l, m ^ (1 << (s[k] - '0')))) {
      r[k] = s[k];
      return true;
    }
    for (int i = s[k] - '0' - 1; i >= 0; --i) {
      if (!i && k == 0) {
        r[k] = r[k + 1] = 0;
        assert(go(k + 2, true, m));
        return true;
      } else {
        if (go(k + 1, true, m ^ (1 << i))) {
          r[k] = '0' + i;
          return true;
        }
      }
    }
  }
  return false;
}
int main() {
  int tn;
  scanf("%d", &tn);
  while (tn--) {
    scanf("%s", s);
    n = strlen(s);
    v.clear();
    assert(go(0, 0, 0));
    int k = 0;
    while (!r[k]) k++;
    r[n] = 0;
    puts(r + k);
  }
  return 0;
}
