#include <bits/stdc++.h>
using namespace std;
inline bool func(string &s, int n, int ind) {
  int f[10] = {0};
  for (int j = 0; j <= ind; j++) {
    f[s[j] - '0'] ^= 1;
  }
  vector<int> a;
  for (int j = 0; j < 10; j++) {
    if (f[j]) a.push_back(j);
  }
  int m = a.size();
  if (n - ind - 1 < m) return false;
  for (int i = ind + 1; i + m < n; i++) {
    if (s[i] > '0') return true;
  }
  for (int i = 0; i < m; i++) {
    if (s[i + n - m] - '0' > a[i]) return true;
    if (s[i + n - m] - '0' < a[i]) return false;
  }
  return false;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << setprecision(32);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int n = s.size();
    int l = 0, r = n - 1;
    while (l < r) {
      int m = l + (r - l) / 2;
      if (func(s, n, m)) {
        l = m + 1;
      } else {
        r = m;
      }
    }
    if (l == 0 && s[0] == '1') {
      for (int i = 2; i < n; i++) {
        cout << '9';
      }
      cout << '\n';
      continue;
    }
    int f[10] = {0};
    for (int i = 0; i < l; i++) {
      f[s[i] - '0'] ^= 1;
    }
    int cnt = 0;
    for (int i = 0; i < 10; i++) {
      if (f[i]) cnt++;
    }
    string t = s.substr(0, l);
    if (n - l == cnt) {
      bool flg = false;
      for (int i = 9; i >= 0; i--) {
        if (f[i] && s[l] - '0' > i) {
          f[i] ^= 1;
          t += char(i + '0');
          flg = true;
          break;
        }
      }
      for (int i = 9; i >= 0; i--) {
        if (f[i]) t += char('0' + i);
      }
      cout << t << '\n';
    } else {
      int x = s[l] - '0' - 1;
      t += char('0' + x);
      f[x] ^= 1;
      if (f[x])
        cnt++;
      else
        cnt--;
      int tmp = n - l - 1 - cnt;
      while (tmp--) {
        t += '9';
      }
      for (int i = 9; i >= 0; i--) {
        if (f[i]) t += char('0' + i);
      }
      cout << t << '\n';
    }
  }
  return 0;
}
