#include <bits/stdc++.h>
using namespace std;
long long modx(long long Base, long long exponent) {
  long long ans = 1;
  if (Base == 1) return Base;
  while (exponent) {
    if (exponent & 1) ans = (ans * Base) % 1000000007LL;
    Base = (Base * Base) % 1000000007LL;
    exponent = exponent >> 1;
  }
  return ans;
}
long long inmodx(long long num) { return (modx(num, 1000000007LL - 2LL)); }
bool cmp() {
  bool ans = 0;
  return ans;
}
const int N = (2e5) + 9;
const int M = (N << 2) + 9;
const int LOGN = ((int)log2(N)) + 3;
const int LOGM = ((int)log2(M)) + 3;
const int BUCK = 450;
string s;
int cnt[N][10], a[N], odd;
bool mark[10];
bool check(int ind, int n) {
  if (odd > (n - ind + 1)) return 0;
  if (a[ind] == 0) return 0;
  int i, j, k;
  if (odd < (n - ind + 1)) {
    a[ind]--;
    if (mark[a[ind]]) {
      mark[a[ind]] = 0;
      odd--;
    } else {
      mark[a[ind]] = 1;
      odd++;
    }
    for (j = (ind + 1); j < (n - odd + 1); j++) a[j] = 9;
    k = 9;
    for (j = (n - odd + 1); j < (n + 1); j++) {
      while (k >= 0) {
        if (mark[k]) break;
        k--;
      }
      a[j] = k;
      mark[k] = 0;
    }
    return 1;
  }
  for (i = a[ind] - 1; i >= 0; i--) {
    if (mark[i]) {
      a[ind] = i;
      mark[i] = 0;
      k = 9;
      for (j = (ind + 1); j < (n + 1); j++) {
        while (k >= 0) {
          if (mark[k]) break;
          k--;
        }
        a[j] = k;
        mark[k] = 0;
      }
      return 1;
    }
  }
  return 0;
}
void solve() {
  int n, i, j;
  cin >> s;
  n = s.length();
  for (i = (1); i < (n + 1); i++) {
    a[i] = s[i - 1] - '0';
    for (j = (0); j < (10); j++) cnt[i][j] = cnt[i - 1][j];
    cnt[i][a[i]]++;
  }
  for (i = n; i > 0; i--) {
    odd = 0;
    for (j = (0); j < (10); j++) mark[j] = 0;
    for (j = (0); j < (10); j++)
      if (cnt[i - 1][j] & 1) {
        odd++;
        mark[j] = 1;
      }
    if (check(i, n)) {
      if (a[1] == 0) {
        for (i = (1); i < (n + 1 - 2); i++) cout << 9;
        cout << '\n';
        return;
      }
      for (i = (1); i < (n + 1); i++) cout << a[i];
      cout << '\n';
      return;
    }
  }
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}
