#include <bits/stdc++.h>
using namespace std;
const int M = 2e5 + 44;
const int N = 14;
char str[M];
int s[M], len;
int cnt[N], ned;
int ans[M];
void fillAns() {
  int pi = len;
  for (int i = 0; i <= 9; i++)
    while (cnt[i]--) ans[pi--] = i;
  while (ans[pi] == -1) ans[pi] = 9, pi--;
}
bool dfs(int id) {
  if (id == len + 1) return true;
  bool flag;
  int pi, now = s[id];
  if (cnt[now])
    cnt[now]--, ned--, ans[id] = now;
  else
    cnt[now]++, ned++, ans[id] = now;
  if (ned <= len - id + 1) {
    flag = dfs(id + 1);
    if (flag) return true;
  }
  if (cnt[now])
    cnt[now]--, ned--, ans[id] = -1;
  else
    cnt[now]++, ned++, ans[id] = -1;
  while (now - 1 >= 0) {
    now--;
    if (cnt[now])
      cnt[now]--, ned--, ans[id] = now;
    else
      cnt[now]++, ned++, ans[id] = now;
    if (ned <= len - id + 1) return true;
    if (cnt[now])
      cnt[now]--, ned--, ans[id] = -1;
    else
      cnt[now]++, ned++, ans[id] = -1;
  }
  return false;
}
void solve() {
  memset(cnt, 0, sizeof(cnt));
  ned = 0;
  memset(ans, -1, sizeof(int) * (len + 22));
  dfs(1);
  fillAns();
  for (int i = 1; i <= len; i++) printf("%d", ans[i]);
  puts("");
}
int main() {
  int ex0, ex1;
  int cas;
  scanf("%d", &cas);
  for (int icas = 1; icas <= cas; icas++) {
    scanf("%s", str + 1);
    len = strlen(str + 1);
    for (int i = 1; i <= len; i++) s[i] = str[i] - '0';
    int pi = len;
    s[pi]--;
    while (s[pi] < 0) {
      s[pi] += 10;
      pi--;
      s[pi]--;
    }
    ex0 = ex1 = 0;
    for (int i = 1; i <= len; i++)
      if (s[i] == 0)
        ex0++;
      else if (s[i] == 1)
        ex1++;
    if (s[1] == 0 || (ex0 + ex1 == len && ex1 == 1)) {
      for (int i = 1; i <= len - 2; i++) printf("9");
      puts("");
    } else if (len & 1) {
      for (int i = 1; i <= len - 1; i++) printf("9");
      puts("");
    } else
      solve();
  }
  return 0;
}
