#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
char s[maxn];
int n, flag = 0;
int getnum(int cnt[]) {
  int odd = 0;
  for (int i = 0; i < 10; ++i)
    if (cnt[i] & 1) odd++;
  return odd;
}
int getsum(int cnt[]) {
  int k = 0;
  for (int i = 0; i < 10; ++i) k += cnt[i];
  return k;
}
int way[maxn];
void dfs(int pos, int cnt[], bool limt, bool ok) {
  int tp = getnum(cnt);
  int tl = n - pos + getsum(cnt);
  if (!ok && tl & 1) return;
  if ((tp > n - pos) || flag) return;
  if (pos == n) {
    if (!tp && !limt) {
      flag = 1;
      int k = 0;
      while (!way[k]) k++;
      for (int i = k; i < n; ++i) printf("%d", way[i]);
      puts("");
    }
    return;
  }
  int top = limt ? s[pos] - '0' : 9;
  for (int i = top; i >= 0; --i) {
    way[pos] = i;
    bool ne = (ok && i == 0);
    if (!ne) cnt[i]++;
    dfs(pos + 1, cnt, limt && i == top, ne);
    if (!ne) cnt[i]--;
  }
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    flag = 0;
    scanf("%s", s);
    n = strlen(s);
    int cnt[10];
    memset(cnt, 0, sizeof cnt);
    dfs(0, cnt, 1, 1);
  }
  return 0;
}
