#include <bits/stdc++.h>
using namespace std;
template <class T>
int size(const T &x) {
  return x.size();
}
const int INF = ~(1 << 31);
const double pi = acos(-1);
const double EPS = 1e-9;
bool check2(string s) {
  int ok = false;
  if (s[0] != '1') ok = true;
  for (int i = (1); i < (s.size() - 1); i++) {
    if (s[i] != '0') ok = true;
  }
  if (!ok) {
    if (s[s.size() - 1] == '1' || s[s.size() - 1] == '0') {
    } else
      ok = true;
  }
  return ok;
}
string s;
bool found = false;
string ans = "";
vector<vector<vector<bool>>> memo;
int dp(int at, int upper, int bt) {
  if (at >= s.size()) {
    if (bt == 0 && upper) {
      found = true;
      return 1;
    }
    return 0;
  }
  if (memo[at][upper][bt]) return 0;
  for (int i = (upper ? 9 : s[at] - '0'); i >= 0; i--) {
    int nebt = bt ^ (1 << i);
    int got = dp(at + 1, max(upper, (i != s[at] - '0' ? 1 : 0)), nebt);
    if (got == 1) {
      ans.push_back(char(i + '0'));
      return 1;
    }
  }
  memo[at][upper][bt] = true;
  return 0;
}
int main() {
  cin.sync_with_stdio(false);
  int t;
  cin >> t;
  for (int i = (0); i < (t); i++) {
    cin >> s;
    if (int(s.size()) % 2 == 1) {
      for (int j = (0); j < (int(s.size()) - 1); j++) {
        cout << "9";
      }
      cout << endl;
      continue;
    } else if (!check2(s)) {
      for (int j = (0); j < (int(s.size()) - 2); j++) {
        cout << "9";
      }
      cout << endl;
    } else {
      for (int i = (0); i < (s.size()); i++) {
        vector<vector<bool>> ok;
        for (int j = (0); j < (2); j++) {
          vector<bool> arr = vector<bool>(1050, 0);
          ok.push_back(arr);
        }
        memo.push_back(ok);
      }
      found = false;
      ans.clear();
      dp(0, 0, 0);
      reverse(ans.begin(), ans.end());
      cout << ans << endl;
      memo.clear();
    }
  }
  return 0;
}
