#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long powmod(long long a, long long b, long long MOD) {
  if (a == 0ll) {
    return 0ll;
  }
  a %= MOD;
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = ans * a % MOD;
    }
    a = a * a % MOD;
    b >>= 1;
  }
  return ans;
}
long long poww(long long a, long long b) {
  if (a == 0ll) {
    return 0ll;
  }
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = ans * a;
    }
    a = a * a;
    b >>= 1;
  }
  return ans;
}
void Pv(const vector<int> &V) {
  int Len = int(V.size());
  for (int i = 0; i < Len; ++i) {
    printf("%d", V[i]);
    if (i != Len - 1) {
      printf(" ");
    } else {
      printf("\n");
    }
  }
}
void Pvl(const vector<long long> &V) {
  int Len = int(V.size());
  for (int i = 0; i < Len; ++i) {
    printf("%lld", V[i]);
    if (i != Len - 1) {
      printf(" ");
    } else {
      printf("\n");
    }
  }
}
inline long long readll() {
  long long tmp = 0, fh = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') fh = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar();
  return tmp * fh;
}
inline int readint() {
  int tmp = 0, fh = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') fh = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar();
  return tmp * fh;
}
void pvarr_int(int *arr, int n, int strat = 1) {
  if (strat == 0) {
    n--;
  }
  for (int i = strat; i <= n; i++) {
    printf("%d%c", arr[i], i == n ? '\n' : ' ');
  }
}
void pvarr_LL(long long *arr, int n, int strat = 1) {
  if (strat == 0) {
    n--;
  }
  for (int i = strat; i <= n; i++) {
    printf("%lld%c", arr[i], i == n ? '\n' : ' ');
  }
}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
char s[maxn];
int n;
bool solve(int id, int info, int last, int eq) {
  if (!eq) {
    if (id + __builtin_popcount(info) <= n) {
      for (int i = 0; i <= id - 2; i++) {
        printf("%c", s[i]);
      }
      printf("%d", last);
      int rm = n - id - __builtin_popcount(info);
      while (rm--) {
        printf("9");
      }
      for (int i = 9; i >= 0; --i) {
        if ((1 << i) & info) {
          printf("%d", i);
        }
      }
      printf("\n");
      return 1;
    }
    return 0;
  }
  for (int i = s[id] - '0'; i >= 0 + (!id); --i) {
    if (solve(id + 1, info ^ (1 << i), i, eq & (i == s[id] - '0'))) {
      return 1;
    }
  }
  return 0;
}
int main() {
  int t;
  t = readint();
  while (t--) {
    scanf("%s", s);
    n = strlen(s);
    if (!solve(0, 0, -1, 1)) {
      for (int i = 1; i <= n - 2; i++) {
        printf("9");
      }
      printf("\n");
    }
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long powmod(long long a, long long b, long long MOD) {
  if (a == 0ll) {
    return 0ll;
  }
  a %= MOD;
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = ans * a % MOD;
    }
    a = a * a % MOD;
    b >>= 1;
  }
  return ans;
}
long long poww(long long a, long long b) {
  if (a == 0ll) {
    return 0ll;
  }
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = ans * a;
    }
    a = a * a;
    b >>= 1;
  }
  return ans;
}
void Pv(const vector<int> &V) {
  int Len = int(V.size());
  for (int i = 0; i < Len; ++i) {
    printf("%d", V[i]);
    if (i != Len - 1) {
      printf(" ");
    } else {
      printf("\n");
    }
  }
}
void Pvl(const vector<long long> &V) {
  int Len = int(V.size());
  for (int i = 0; i < Len; ++i) {
    printf("%lld", V[i]);
    if (i != Len - 1) {
      printf(" ");
    } else {
      printf("\n");
    }
  }
}
inline long long readll() {
  long long tmp = 0, fh = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') fh = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar();
  return tmp * fh;
}
inline int readint() {
  int tmp = 0, fh = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') fh = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar();
  return tmp * fh;
}
void pvarr_int(int *arr, int n, int strat = 1) {
  if (strat == 0) {
    n--;
  }
  for (int i = strat; i <= n; i++) {
    printf("%d%c", arr[i], i == n ? '\n' : ' ');
  }
}
void pvarr_LL(long long *arr, int n, int strat = 1) {
  if (strat == 0) {
    n--;
  }
  for (int i = strat; i <= n; i++) {
    printf("%lld%c", arr[i], i == n ? '\n' : ' ');
  }
}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
char s[maxn];
int n;
bool solve(int id, int info, int last, int eq) {
  if (!eq) {
    if (id + __builtin_popcount(info) <= n) {
      for (int i = 0; i <= id - 2; i++) {
        printf("%c", s[i]);
      }
      printf("%d", last);
      int rm = n - id - __builtin_popcount(info);
      while (rm--) {
        printf("9");
      }
      for (int i = 9; i >= 0; --i) {
        if ((1 << i) & info) {
          printf("%d", i);
        }
      }
      printf("\n");
      return 1;
    }
    return 0;
  }
  for (int i = s[id] - '0'; i >= 0 + (!id); --i) {
    if (solve(id + 1, info ^ (1 << i), i, eq & (i == s[id] - '0'))) {
      return 1;
    }
  }
  return 0;
}
int main() {
  int t;
  t = readint();
  while (t--) {
    scanf("%s", s);
    n = strlen(s);
    if (!solve(0, 0, -1, 1)) {
      for (int i = 1; i <= n - 2; i++) {
        printf("9");
      }
      printf("\n");
    }
  }
  return 0;
}

```