#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    string trash;
    cin >> trash;
    int l = trash.length();
    vector<int> s;
    for (int j = 0; j < l; j++) s.push_back(trash[j] - '0');
    bool bad = true;
    if (s[0] != 1) bad = false;
    for (int j = 1; j < l - 1; j++) {
      if (s[j] != 0) bad = false;
    }
    if (s[l - 1] != 0 && s[l - 1] != 1) bad = false;
    if (bad) {
      for (int j = 0; j < l - 2; j++) cout << '9';
      cout << endl;
    } else {
      int check[10], freq[10], carry[10];
      for (int j = 0; j < 10; j++) check[j] = 0, freq[j] = 0;
      bool possible = true;
      int maxl = 0;
      freq[0] = l;
      for (int j = 0; j < l; j++) {
        if (check[s[j]] == 1) {
          check[s[j]] = 0;
          freq[s[j]]--;
        } else {
          check[s[j]] = 1;
          freq[s[j]]++;
          freq[0] -= 2;
          if (freq[0] < 0) {
            possible = false;
            break;
          }
        }
        if (possible && s[j] != 0) {
          for (int u = 0; u < 10; u++) carry[u] = freq[u];
          for (int u = j + 1; u < l; u++) {
            bool skip = false;
            for (int v = 0; v < s[u]; v++) {
              if (carry[v] > 0) {
                skip = true;
                break;
              }
            }
            if (skip) break;
            if (carry[s[u]] > 0)
              carry[s[u]]--;
            else {
              possible = false;
              break;
            }
            if (u == l - 1) possible = false;
          }
        }
        if (!possible)
          break;
        else
          maxl = j + 1;
      }
      vector<int> ans;
      for (int j = 0; j < 10; j++) check[j] = 0;
      for (int j = 0; j < maxl; j++) {
        ans.push_back(s[j]);
        check[s[j]] = 1 - check[s[j]];
      }
      if (maxl < l) {
        int sum = 0;
        for (int j = 0; j < 10; j++) sum += check[j];
        if (sum == l - maxl) {
          int cur = s[maxl] - 1;
          while (check[cur] == 0) cur--;
          check[cur]--;
          ans.push_back(cur);
        } else {
          ans.push_back(s[maxl] - 1);
          sum += (1 - 2 * check[s[maxl] - 1]);
          check[s[maxl] - 1] = 1 - check[s[maxl] - 1];
          check[9] += l - maxl - 1 - sum;
        }
        for (int j = maxl + 1; j < l; j++) {
          for (int u = 9; u >= 0; u--) {
            if (check[u] > 0) {
              ans.push_back(u);
              check[u]--;
              break;
            }
          }
        }
      }
      for (int j = 0; j < l; j++) cout << ans[j];
      cout << endl;
    }
  }
  return 0;
}
