#include <bits/stdc++.h>
using namespace std;
template <typename c>
void amax(c &x, c y) {
  x = max(x, y);
}
template <typename c>
void amin(c &x, c y) {
  x = min(x, y);
}
string s;
vector<char> ans;
int n;
bool go(int i, bool eq, int mask) {
  if (i == n) return !eq && mask == 0;
  int rem = __builtin_popcount(mask);
  int fil = n - i - rem;
  if (fil < 0 || fil & 1) return false;
  if (eq) {
    ans.emplace_back(s[i]);
    if (go(i + 1, eq, mask ^ (1 << (s[i] - '0')))) return true;
    ans.pop_back();
    for (int j = s[i] - '0' - 1; ~j; j--) {
      ans.emplace_back('0' + j);
      if (go(i + 1, 0, mask ^ (1 << j))) return true;
      ans.pop_back();
    }
    return false;
  }
  while (fil--) ans.emplace_back('9');
  for (int j = 11; ~j; j--)
    if (mask >> j & 1) ans.emplace_back('0' + j);
  return true;
}
void solve() {
  cin >> s;
  n = (int)(s).size();
  ans.clear();
  if (go(0, 1, 0) && ans[0] != '0') {
    for (auto x : ans) cout << x;
    cout << endl;
  } else
    cout << string(n - 2, '9') << endl;
}
int32_t main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int tc;
  cin >> tc;
  while (tc--) solve();
  return 0;
}
