#include <bits/stdc++.h>
using namespace std;
const int N = 200 * 1000 + 13;
int n;
int cnt[10];
string s, t;
int pr0[N];
bool check(int pos) {
  int c = accumulate(cnt, cnt + 10, 0);
  if (c > n - pos) return false;
  if (pr0[n - c] - pr0[pos] > 0) return true;
  int nxt = 0;
  for (int i = n - c; i < n; ++i, ++nxt) {
    while (cnt[nxt] == 0) ++nxt;
    if (s[i] > '0' + nxt) return true;
    if (s[i] < '0' + nxt) return false;
  }
  return false;
}
bool can(int pos) {
  int c = accumulate(cnt, cnt + 10, 0);
  return (c <= n - pos);
}
void fix(int pos) {
  int c = accumulate(cnt, cnt + 10, 0);
  t += string(n - pos - c, '9');
  int nxt = 9;
  while (nxt >= 0) {
    while (nxt >= 0 && cnt[nxt] == 0) --nxt;
    if (nxt >= 0) {
      t += '0' + nxt;
      --nxt;
    }
  }
}
char buf[N];
bool read() {
  if (scanf("%s", buf) != 1) return false;
  s = buf;
  n = s.size();
  return true;
}
void solve() {
  t = "";
  pr0[0] = 0;
  for (int i = 0; i < int(n); i++) pr0[i + 1] = pr0[i] + (s[i] > '0');
  if (s[0] == '1' && pr0[n] == 1) {
    printf("%s\n", string(n - 2, '9').c_str());
    return;
  }
  if (s[0] == '1' && s[n - 1] == '1' && pr0[n] == 2) {
    printf("%s\n", string(n - 2, '9').c_str());
    return;
  }
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < int(n); i++) {
    if (i + 1 < n) {
      cnt[s[i] - '0'] ^= 1;
      if (check(i + 1)) {
        t += s[i];
        continue;
      }
      cnt[s[i] - '0'] ^= 1;
    }
    for (char c = s[i] - 1; c >= '0'; --c) {
      cnt[c - '0'] ^= 1;
      if (can(i + 1)) {
        t += c;
        fix(i + 1);
        break;
      }
      cnt[c - '0'] ^= 1;
    }
    break;
  }
  printf("%s\n", t.c_str());
}
int main() {
  int tc;
  scanf("%d", &tc);
  while (tc--) {
    read();
    solve();
  }
  return 0;
}
