#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1e9;
const int MAXN = (int)2e5 + 10;
char s[MAXN];
int pre_mask[MAXN];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", s);
    int n = strlen(s);
    if (n % 2 == 1) {
      for (int i = 0; i < n - 1; i++) {
        printf("9");
      }
      printf("\n");
    } else {
      int mask = 0;
      for (int i = 0; i < n; i++) {
        mask ^= (1 << (s[i] - '0'));
        pre_mask[i] = mask;
      }
      int done = false;
      for (int i = n - 1; i >= 0; i--) {
        int cur_mask = (i >= 1 ? pre_mask[i - 1] : 0);
        for (int val = s[i] - '0' - 1; val >= (i == 0 ? 1 : 0); val--) {
          cur_mask ^= (1 << val);
          vector<int> digits;
          for (int d = 0; d < 10; d++) {
            if (cur_mask & (1 << d)) {
              digits.push_back(d);
            }
          }
          reverse(digits.begin(), digits.end());
          if (n - i - 1 >= digits.size() &&
              (n - i - 1 - (int)digits.size()) % 2 == 0) {
            string ans = "";
            for (int j = 0; j < i; j++) {
              ans += s[j];
            }
            ans += (char)(val + '0');
            int cnt9 = (n - i - 1 - (int)digits.size());
            for (int j = 0; j < cnt9; j++) {
              ans += "9";
            }
            for (int d : digits) {
              ans += (char)(d + '0');
            }
            assert(ans.size() == n);
            printf("%s\n", ans.c_str());
            done = true;
            goto DONE;
          }
          cur_mask ^= (1 << val);
        }
      }
    DONE:
      if (!done) {
        for (int i = 0; i < n - 2; i++) {
          printf("9");
        }
        printf("\n");
      }
    }
  }
  return 0;
}
