#include <bits/stdc++.h>
using namespace std;
char s[200010], t[200010];
char q[50], r[50];
bool ten[10];
int tree[200010];
int len;
int lowbit(int x) { return x & (-x); }
void update(int x, int val) {
  for (int i = x; i <= len; i += lowbit(i)) tree[i] += val;
}
int query(int x) {
  int ans = 0;
  for (int i = x; i; i -= lowbit(i)) ans += tree[i];
  return ans;
}
int main() {
  int T;
  cin >> T;
  while (T--) {
    scanf("%s", s);
    len = strlen(s);
    memset(ten, false, sizeof(ten));
    for (int i = 0; i < len; i++) t[i] = '0';
    t[len] = '\n';
    for (int i = 1; i <= len; i++) tree[i] = 0;
    for (int i = 1; i <= len; i++) {
      int p = s[i - 1] - 48;
      update(i, p);
    }
    bool flag = false;
    for (int i = 0; i < len; i++) {
      for (int j = 9; j >= 0; j--) {
        ten[j] = !ten[j];
        int cnt = 0;
        for (int k = 0; k < 10; k++)
          if (ten[k]) cnt++;
        if (i + cnt >= len) {
          ten[j] = !ten[j];
          continue;
        }
        cnt = 0;
        for (int k = 0; k < 10; k++) {
          if (ten[k]) {
            r[cnt] = k + 48;
            cnt++;
          }
        }
        r[cnt] = '\0';
        for (int k = len - cnt; k <= len - 1; k++) q[k - len + cnt] = s[k];
        q[cnt] = '\0';
        if (flag) {
          t[i] = j + 48;
          break;
        }
        if (j + 48 < s[i]) {
          t[i] = j + 48;
          break;
        }
        if (j + 48 > s[i]) {
          ten[j] = !ten[j];
          continue;
        }
        if (i + cnt != len) {
          int qaq = query(len - cnt) - query(i + 1);
          if (qaq) {
            t[i] = j + 48;
            break;
          }
        }
        if (strcmp(r, q) < 0) {
          t[i] = j + 48;
          break;
        }
        ten[j] = !ten[j];
      }
      if (t[i] < s[i]) flag = true;
    }
    bool lead = false;
    int m;
    for (m = 0; m < len; m++)
      if (t[m] != '0') break;
    for (int i = m; i < len - m; i++) printf("%c", t[i]);
    printf("\n");
  }
  return 0;
}
