#include <bits/stdc++.h>
using namespace std;
int t;
vector<vector<int>> nums;
void Load() {
  scanf("%d", &t);
  nums.resize(t);
  for (int i = 0; i < t; ++i) {
    char num[200001];
    scanf("%s", num);
    int cur = 0;
    while (num[cur] != '\0') {
      nums[i].push_back(num[cur] - '0');
      cur++;
    }
  }
}
void Solve() {
  for (const auto& num : nums) {
    vector<int> digitcount(10, 0);
    for (int digit : num) digitcount[digit]++;
    bool cando = false;
    for (int i = 1; i <= num.size(); ++i) {
      digitcount[num[num.size() - i]]--;
      if (num[num.size() - i] == 0) continue;
      if (i == num.size()) {
        cando = true;
        if (num[0] == 1) {
          for (int j = 0; j < num.size() - 2; ++j) {
            printf("9");
          }
          puts("");
          break;
        }
        printf("%d", num[0] - 1);
        for (int j = 0; j < num.size() - 2; ++j) {
          printf("9");
        }
        printf("%d", num[0] - 1);
        puts("");
        break;
      }
      const int spec = num[num.size() - i];
      int num_ones = 0, min_one = 10;
      for (int j = 0; j < 10; ++j) {
        if (digitcount[j] % 2 == 1) {
          num_ones++;
          min_one = min(j, min_one);
        }
      }
      const int num_free = i - num_ones;
      if (num_free < 0) continue;
      if (num_free == 0 && min_one >= spec) continue;
      cando = true;
      for (int j = 0; j < num.size() - i; ++j) printf("%d", num[j]);
      if (num_free > 0) {
        printf("%d", spec - 1);
        digitcount[spec - 1]++;
        num_ones = 0;
        for (int j = 0; j < 10; ++j) {
          if (digitcount[j] % 2 == 1) {
            num_ones++;
          }
        }
        for (int j = num_ones + 1; j < i; ++j) printf("9");
        for (int j = 9; j >= 0; --j) {
          if (digitcount[j] % 2 == 1) printf("%d", j);
        }
        digitcount[spec - 1]--;
      } else {
        int firstput = 10;
        for (int j = 0; j < 10; ++j) {
          if (digitcount[j] % 2 == 1 && j < spec) firstput = j;
        }
        printf("%d", firstput);
        for (int j = 9; j >= 0; --j) {
          if (digitcount[j] % 2 == 1 && j != firstput) printf("%d", j);
        }
      }
      puts("");
      break;
    }
    if (!cando) {
      for (int i = 0; i < num.size() - 2; ++i) printf("9");
      puts("");
    }
  }
}
int main() {
  Load();
  Solve();
  return 0;
}
