#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  string s;
  for (int i = 0; i < t; ++i) {
    cin >> s;
    int n = s.length();
    bool is_round = s[0] == '1';
    for (int i = 1; i < n - 1; ++i) {
      if (s[i] != '0') {
        is_round = false;
        break;
      }
    }
    if (s[n - 1] != '0' && s[n - 1] != '1') {
      is_round = false;
    }
    if (is_round) {
      for (int i = 0; i < (n - 1) / 2 * 2; ++i) {
        cout << 9;
      }
      cout << '\n';
      continue;
    }
    map<char, int> cnt;
    for (int i = 0; i < n; ++i) {
      ++cnt[s[i]];
    }
    int odd_cnt = 0;
    for (auto &item : cnt) {
      odd_cnt += item.second % 2;
    }
    for (int i = n - 1; i >= 0; --i) {
      char cur = s[i];
      if (cnt[cur]-- % 2) {
        --odd_cnt;
      } else {
        ++odd_cnt;
      }
      if (cur == '0') {
        continue;
      }
      char odd_handle = ' ';
      for (char c = cur - 1; c >= '0'; --c) {
        if (cnt[c] % 2) {
          odd_handle = c;
          break;
        }
      }
      if (odd_handle != cur - 1 && odd_cnt <= n - i - 2 &&
          (n - i - 2 - odd_cnt) % 2 == 0) {
        ++cnt[--s[i]];
        vector<int> odd;
        for (char c = '0'; c <= '9'; ++c) {
          if (cnt[c] % 2) {
            odd.push_back(c);
          }
        }
        sort(odd.begin(), odd.end());
        int j = i + 1;
        for (; j < i + 1 + odd.size(); ++j) {
          s[j] = odd[j - i - 1];
        }
        for (; j < n; ++j) {
          s[j] = '9';
        }
        reverse(s.begin() + i + 1, s.end());
        cout << s << '\n';
        break;
      }
      if (odd_handle != ' ' && odd_cnt <= n - i && (n - i - odd_cnt + 1) % 2) {
        ++cnt[s[i] = odd_handle];
        vector<int> odd;
        for (char c = '0'; c <= '9'; ++c) {
          if (cnt[c] % 2) {
            odd.push_back(c);
          }
        }
        sort(odd.begin(), odd.end());
        int j = i + 1;
        for (; j < i + 1 + odd.size(); ++j) {
          s[j] = odd[j - i - 1];
        }
        for (; j < n; ++j) {
          s[j] = '9';
        }
        reverse(s.begin() + i + 1, s.end());
        cout << s << '\n';
        break;
      }
    }
  }
  return 0;
}
