#include <bits/stdc++.h>
using namespace std;
int main() {
  int ii, n, i, m, j, k, z = 0, c = 0, t, x, y, l, r, mid, d;
  scanf("%d", &t);
  while (t--) {
    string s;
    cin >> s;
    vector<int> v;
    int a[10] = {0};
    n = s.size() - 1;
    for (i = 0; i <= n; i++) a[s[i] - 48]++;
    for (i = n; i >= 0; i--) {
      x = s[i] - 48;
      a[x]--;
      c = 0;
      for (j = 0; j < 10; j++) {
        if (a[j] & 1) c++;
      }
      z = n - i + 1;
      if (c > z) continue;
      if (x == 0) continue;
      if (i == 0 && x == 1) continue;
      if (c == z) {
        for (j = x - 1; j >= 0; j--) {
          if (a[j] & 1) {
            s[i++] = char(48 + j);
            a[j]++;
            for (j = 9; j >= 0; j--) {
              if (a[j] & 1) s[i++] = char(j + 48);
            }
            cout << s << endl;
            goto jmp;
          }
        }
        continue;
      }
      s[i++] = char(x + 47);
      a[x - 1]++;
      if (a[x - 1] & 1) c++;
      i = n;
      z--;
      for (j = 0; j < 10; j++) {
        if (a[j] & 1) {
          c--;
          z--;
          s[i--] = char(j + 48);
        }
      }
      while (z--) s[i--] = char(57);
      cout << s << endl;
      goto jmp;
    }
    n -= 1;
    for (i = 0; i < n; i++) cout << 9;
    printf("\n");
  jmp:
    i = 0;
  }
}
