#include <bits/stdc++.h>
using namespace std;
int t, l, ans, a[10], c[10];
char s[200001];
bool b;
int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%s", s + 1);
    l = strlen(s + 1);
    if (l == 1) {
      printf("%d\n", s[1] - 48);
      continue;
    }
    if (l & 1) {
      for (int i = 2; i <= l; i += 2) printf("99");
      printf("\n");
      continue;
    }
    if (s[1] == '1') {
      if (l == 2 && (s[2] == '1' || s[2] == '0')) {
        printf("9\n");
        continue;
      }
      b = true;
      for (int i = 2; i <= l - 1; i++)
        if (s[i] != '0') {
          b = false;
          break;
        }
      if (b == true && (s[l] == '1' || s[l] == '0')) {
        for (int i = 1; i <= l - 2; i += 2) printf("99");
        printf("\n");
        continue;
      }
    }
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= l; i++) a[s[i] - 48]++;
    b = false;
    for (int k = 1; k <= l; k++)
      if (s[l - k + 1] != '0') {
        for (int i = 0; i <= 9; i++) c[i] = a[i];
        for (int i = 1; i <= k; i++) c[s[l - i + 1] - 48]--;
        for (int j = s[l - k + 1] - 49; j >= 0; j--) {
          c[j]++;
          ans = 0;
          for (int i = 0; i <= 8; i++)
            if (c[i] & 1) ans++;
          if (ans <= k - 1) {
            for (int i = 1; i <= l - k; i++) printf("%c", s[i]);
            printf("%d", j);
            for (int i = 1; i <= k - 1 - ans; i++) printf("9");
            for (int i = 8; i >= 0; i--)
              if (c[i] & 1) printf("%d", i);
            printf("\n");
            b = true;
            break;
          }
          c[j]--;
        }
        if (b) break;
      }
  }
  return 0;
}
