#include <bits/stdc++.h>
using namespace std;
char s[210000];
char t[210000];
int n;
int check(int x, int y) {
  int len = n - x, st = x;
  int num = __builtin_popcount(y);
  if (num > len) return 0;
  if (num == len) {
    int now = s[x + 1] - '0';
    int flag = 0;
    for (int i = now - 1; i >= 0; i--)
      if (y & (1 << i)) {
        y ^= 1 << i;
        flag = 1;
        for (int j = 1; j <= x; j++) t[j] = s[j];
        t[++x] = i + '0';
        for (int j = 9; j >= 0; j--)
          if (y & (1 << j)) t[++x] = j + '0', y ^= 1 << j;
        break;
      }
    if (flag == 0) return 0;
    return 1;
  }
  int flag = 0;
  if (s[x + 1] == '0') return 0;
  for (int j = 1; j <= x; j++) t[j] = s[j];
  t[x + 1] = s[x + 1] - 1, y ^= 1 << (s[x + 1] - 1 - '0');
  x++;
  int left = len - 1 - __builtin_popcount(y);
  for (int i = 1; i <= left; i++) t[++x] = '9';
  for (int j = 9; j >= 0; j--)
    if (y & (1 << j)) t[++x] = j + '0', y ^= 1 << j;
  if (st == 0 && t[1] == '0') t[n] = 0;
  return 1;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    int pos = 0;
    for (int i = 1; i < n; i++) pos ^= 1 << (s[i] - '0');
    t[n + 1] = 0;
    for (int i = n - 1; i >= 0; i--) {
      if (check(i, pos)) {
        break;
      }
      pos ^= 1 << (s[i] - '0');
    }
    pos = 0;
    while (t[pos] == 0 || t[pos] == '0') pos++;
    printf("%s\n", t + pos);
  }
  return 0;
}
