#include <bits/stdc++.h>
using namespace std;
const int N = 400010;
int n, idx = 0, frq[10], nxt[N];
char s[N];
bool check(int i, int j, bool less, int num) {
  frq[j] ^= 1;
  if (frq[j])
    num++;
  else
    num--;
  if (n - i - 1 < num) return false;
  if (less) return true;
  if (nxt[i] < n - num) return true;
  idx = 0;
  for (i = n - num; i < n; i++) {
    while (frq[idx] == 0) idx++;
    if (s[i] - '0' > idx)
      return true;
    else if (s[i] - '0' < idx)
      return false;
    idx++;
  }
  return false;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    memset(frq, 0, sizeof(frq));
    scanf("%s", s);
    n = strlen(s);
    if (n & 1) {
      for (int i = 0; i < n - 1; i++) putchar('9');
      puts("");
      continue;
    }
    s[n] = '\0';
    for (int i = n - 1; i >= 0; i--)
      nxt[i] = (s[i + 1] == '0' ? nxt[i + 1] : i + 1);
    bool less = false;
    string ans;
    for (int i = 0; i < n; i++) {
      int chozen = 0, num = 0;
      for (int j = 0; j < 10; j++) num += frq[j];
      bool curless = less;
      for (int j = (!less ? s[i] - '0' : 9); j >= 0; j--) {
        if (j < s[i] - '0') curless = true;
        if (check(i, j, curless, num)) {
          chozen = j;
          break;
        }
        frq[j] ^= 1;
      }
      if (i == 0 && chozen == 0) {
        for (int j = 0; j < n - 2; j++) ans += '9';
        break;
      }
      if (chozen < s[i] - '0') less = true;
      ans += (chozen + '0');
    }
    puts(ans.c_str());
  }
  return 0;
}
