#include <bits/stdc++.h>
using namespace std;
const int N = 200000;
const int A = 10;
char s[N];
bool d[A];
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%s", s);
    int n = strlen(s);
    if (s[0] == '1') {
      int i = 1;
      while (s[i] && s[i] == '0') ++i;
      if (i == n || i == n - 1 && s[i] == '1') {
        for (int i = 0; i < n - 2; ++i) printf("%d", 9);
        printf("\n");
        continue;
      }
    }
    int same = 0;
    for (int i = 0; i < n - 1; ++i) {
      d[s[i] - '0'] = !d[s[i] - '0'];
      int t = 0;
      for (int i = 0; i < A; ++i) t += d[i];
      if (s[i + 1] != '0' && t <= n - i - 1) {
        bool ok = true;
        if (t && t == n - i - 1) {
          ok = false;
          for (int j = 0; j < s[i + 1] - '0'; ++j)
            if (d[j]) ok = true;
        }
        if (ok) same = i + 1;
      }
    }
    assert(s[same] != '0');
    memset(d, 0, A * sizeof(*d));
    for (int i = 0; i < same; ++i) {
      printf("%c", s[i]);
      d[s[i] - '0'] = !d[s[i] - '0'];
    }
    int t = 0;
    for (int i = 0; i < A; ++i) t += d[i];
    if (t == n - same) {
      int i = s[same] - '0' - 1;
      while (i >= 0 && !d[i]) --i;
      assert(i >= 0);
      printf("%d", i);
      d[i] = !d[i];
      t += d[i] * 2 - 1;
    } else {
      printf("%d", s[same] - '0' - 1);
      d[s[same] - '0' - 1] = !d[s[same] - '0' - 1];
      t += d[s[same] - '0' - 1] * 2 - 1;
    }
    ++same;
    while (t < n - same) {
      printf("9");
      d[9] = !d[9];
      t += d[9] * 2 - 1;
      ++same;
    }
    for (int i = A - 1; i >= 0; --i)
      if (d[i]) printf("%d", i);
    memset(d, 0, A * sizeof(*d));
    printf("\n");
  }
  return 0;
}
