#include <bits/stdc++.h>
using namespace std;
vector<int> calc(vector<int>& S, int pt) {
  vector<int> ans;
  int N = S.size();
  bool less = false, nonzero = false;
  int l_zero = 0;
  int stock[10] = {0};
  int sum = 0, anc = 0;
  for (int i = 0; i < N; i++) {
    int mx = less ? 9 : S[i];
    int c1 = mx, c2 = mx - 1;
    if (sum - N % 2 == N - i) {
      c1 = c2 = -1;
      for (int k = mx; k >= 0; k--)
        if (stock[k]) {
          if (c1 == -1) {
            c1 = k;
          } else if (c2 == -1) {
            c2 = k;
            break;
          }
        }
    }
    if ((N - l_zero) % 2) {
      c1 = 0;
      c2 = -1;
    }
    int c = (pt == i ? c2 : c1);
    if (c2 >= 0) anc = i;
    if (c1 == -1) return {-1, anc};
    if (c < S[i]) less = true;
    if (c) {
      nonzero = true;
    } else {
      if (!nonzero) l_zero++;
    }
    if (nonzero) {
      ans.push_back(c);
      if (stock[c]) {
        stock[c]--;
        sum--;
      } else {
        stock[c]++;
        sum++;
      }
    }
  }
  if (less) {
    return ans;
  } else {
    return {-1, anc};
  }
}
void solve() {
  string str;
  cin >> str;
  vector<int> S;
  for (char c : str) S.push_back(c - '0');
  auto ans = calc(S, -1);
  if (ans[0] == -1) ans = calc(S, ans[1]);
  for (int a : ans) printf("%d", a);
  printf("\n");
}
int main() {
  int T;
  cin >> T;
  while (T--) solve();
  return 0;
}
