#include <bits/stdc++.h>
int count[10];
bool is_special(std::string string) {
  if (string[0] != '1' ||
      (string[string.size() - 1] != '0' && string[string.size() - 1] != '1')) {
    return false;
  }
  for (int i = 1; i < (int)string.size() - 1; ++i) {
    if (string[i] != '0') {
      return false;
    }
  }
  return true;
}
int one_cnt() {
  int cnt = 0;
  for (int j = 9; j >= 0; --j) {
    cnt += count[j] & 1;
  }
  return cnt;
}
bool has_one_less(int l) {
  for (int j = 0; j < l; ++j) {
    if (count[j] & 1) {
      return true;
    }
  }
  return false;
}
int main() {
  int T;
  std::cin >> T;
  while (T--) {
    std::string input_string;
    std::cin >> input_string;
    for (int i = 0; i < 10; ++i) {
      count[i] = 0;
    }
    if (is_special(input_string)) {
      for (int i = 0; i < (int)input_string.size() - 2; ++i) {
        std::cout << '9';
      }
      std::cout << std::endl;
      continue;
    }
    for (char c : input_string) {
      count[c - '0'] += 1;
    }
    for (int i = (int)input_string.size() - 1; i >= 0; --i) {
      count[input_string[i] - '0'] -= 1;
      if (one_cnt() == input_string.size() - i &&
          has_one_less(input_string[i] - '0')) {
        for (int j = 0; j < i; ++j) {
          std::cout << input_string[j];
        }
        for (int j = input_string[i] - '0' - 1; j >= 0; --j) {
          if (count[j] & 1) {
            std::cout << j;
            count[j] -= 1;
            break;
          }
        }
        for (int j = 9; j >= 0; --j) {
          if (count[j] & 1) {
            std::cout << j;
          }
        }
        std::cout << std::endl;
        break;
      }
      if (one_cnt() < input_string.size() - i && input_string[i] != '0') {
        for (int j = 0; j < i; ++j) {
          std::cout << input_string[j];
        }
        std::cout << input_string[i] - '0' - 1;
        count[input_string[i] - '0' - 1] -= 1;
        for (int j = input_string.size() - i - one_cnt() - 1; j > 0; --j) {
          std::cout << 9;
        }
        for (int j = 9; j >= 0; --j) {
          if (count[j] & 1) {
            std::cout << j;
          }
        }
        std::cout << std::endl;
        break;
      }
    }
  }
  return 0;
}
