#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
template <typename T>
bool mmax(T &m, const T q) {
  if (m < q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T>
bool mmin(T &m, const T q) {
  if (m > q) {
    m = q;
    return true;
  } else
    return false;
}
void __print(long long first) { cerr << first; }
void __print(long first) { cerr << first; }
void __print(unsigned first) { cerr << first; }
void __print(unsigned long first) { cerr << first; }
void __print(unsigned long long first) { cerr << first; }
void __print(float first) { cerr << first; }
void __print(double first) { cerr << first; }
void __print(long double first) { cerr << first; }
void __print(char first) { cerr << '\'' << first << '\''; }
void __print(const char *first) { cerr << '\"' << first << '\"'; }
void __print(const string &first) { cerr << '\"' << first << '\"'; }
void __print(bool first) { cerr << (first ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &first) {
  cerr << '{';
  __print(first.first);
  cerr << ',';
  __print(first.second);
  cerr << '}';
}
template <typename T>
void __print(const T &first) {
  long long f = 0;
  cerr << '{';
  for (auto &i : first) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
long long dx[] = {0, 0, 1, -1};
long long dy[] = {1, -1, 0, 0};
const long long N = 2e5 + 5;
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long T;
  cin >> T;
  while (T--) {
    string s;
    cin >> s;
    long long n = s.size();
    vector<vector<long long> > p(10, vector<long long>(n + 1, 0));
    for (long long i = 1; i <= n; i++) {
      long long d = s[i - 1] - '0';
      p[d][i] = 1;
    }
    for (long long i = 0; i < 10; i++) {
      for (long long j = 1; j <= n; j++) p[i][j] += p[i][j - 1];
    }
    bool flag = false;
    for (long long j = n; j >= 1; j--) {
      long long d = s[j - 1] - '0';
      if (j == 1 and d == 1) break;
      long long r = n - j;
      for (long long pos = d - 1; pos >= 0; pos--) {
        vector<long long> mark(10);
        long long cnt = 0;
        for (long long c = 0; c < 10; c++) {
          if (pos == c) {
            if ((p[c][j - 1] + 1) & 1) {
              cnt++;
              mark[c] = 1;
            }
          } else if ((p[c][j - 1]) & 1) {
            cnt++;
            mark[c] = 1;
          }
        }
        if (cnt <= r) {
          long long suf = r - cnt;
          if (suf % 2 == 0) {
            cout << s.substr(0, j - 1) << pos;
            for (long long k = 0; k < suf; k++) cout << 9;
            for (long long k = 9; k >= 0; k--) {
              if (mark[k]) cout << k;
            }
            cout << "\n";
            flag = true;
            break;
          }
        }
      }
      if (flag) break;
    }
    if (!flag) {
      for (long long i = 0; i < n - 2; i++) cout << 9;
      cout << "\n";
      continue;
    }
  }
  return 0;
}

### Prompt

Generate a cpp solution to the following problem:

Yes, that's another problem with definition of "beautiful" numbers.

Let's call a positive integer x beautiful if its decimal representation without leading zeroes contains even number of digits, and there exists a permutation of this representation which is palindromic. For example, 4242 is a beautiful number, since it contains 4 digits, and there exists a palindromic permutation 2442.

Given a positive integer s, find the largest beautiful number which is less than s.

Input

The first line contains one integer t (1 ≤ t ≤ 105) — the number of testcases you have to solve.

Then t lines follow, each representing one testcase and containing one string which is the decimal representation of number s. It is guaranteed that this string has even length, contains no leading zeroes, and there exists at least one beautiful number less than s.

The sum of lengths of s over all testcases doesn't exceed 2·105.

Output

For each testcase print one line containing the largest beautiful number which is less than s (it is guaranteed that the answer exists).

Example

Input

4
89
88
1000
28923845


Output

88
77
99
28923839

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
template <typename T>
bool mmax(T &m, const T q) {
  if (m < q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T>
bool mmin(T &m, const T q) {
  if (m > q) {
    m = q;
    return true;
  } else
    return false;
}
void __print(long long first) { cerr << first; }
void __print(long first) { cerr << first; }
void __print(unsigned first) { cerr << first; }
void __print(unsigned long first) { cerr << first; }
void __print(unsigned long long first) { cerr << first; }
void __print(float first) { cerr << first; }
void __print(double first) { cerr << first; }
void __print(long double first) { cerr << first; }
void __print(char first) { cerr << '\'' << first << '\''; }
void __print(const char *first) { cerr << '\"' << first << '\"'; }
void __print(const string &first) { cerr << '\"' << first << '\"'; }
void __print(bool first) { cerr << (first ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &first) {
  cerr << '{';
  __print(first.first);
  cerr << ',';
  __print(first.second);
  cerr << '}';
}
template <typename T>
void __print(const T &first) {
  long long f = 0;
  cerr << '{';
  for (auto &i : first) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
long long dx[] = {0, 0, 1, -1};
long long dy[] = {1, -1, 0, 0};
const long long N = 2e5 + 5;
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long T;
  cin >> T;
  while (T--) {
    string s;
    cin >> s;
    long long n = s.size();
    vector<vector<long long> > p(10, vector<long long>(n + 1, 0));
    for (long long i = 1; i <= n; i++) {
      long long d = s[i - 1] - '0';
      p[d][i] = 1;
    }
    for (long long i = 0; i < 10; i++) {
      for (long long j = 1; j <= n; j++) p[i][j] += p[i][j - 1];
    }
    bool flag = false;
    for (long long j = n; j >= 1; j--) {
      long long d = s[j - 1] - '0';
      if (j == 1 and d == 1) break;
      long long r = n - j;
      for (long long pos = d - 1; pos >= 0; pos--) {
        vector<long long> mark(10);
        long long cnt = 0;
        for (long long c = 0; c < 10; c++) {
          if (pos == c) {
            if ((p[c][j - 1] + 1) & 1) {
              cnt++;
              mark[c] = 1;
            }
          } else if ((p[c][j - 1]) & 1) {
            cnt++;
            mark[c] = 1;
          }
        }
        if (cnt <= r) {
          long long suf = r - cnt;
          if (suf % 2 == 0) {
            cout << s.substr(0, j - 1) << pos;
            for (long long k = 0; k < suf; k++) cout << 9;
            for (long long k = 9; k >= 0; k--) {
              if (mark[k]) cout << k;
            }
            cout << "\n";
            flag = true;
            break;
          }
        }
      }
      if (flag) break;
    }
    if (!flag) {
      for (long long i = 0; i < n - 2; i++) cout << 9;
      cout << "\n";
      continue;
    }
  }
  return 0;
}

```