CF946E.Largest Beautiful Number

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.

是的，这又是“优美”数定义中的另一个问题。

我们称一个正整数 $x$ 是优美数，如果它在不带前导零的十进制表示中包含偶数个数字，且该表示存在一种排列，使得该排列构成回文。例如，$4242$ 是一个优美数，因为它包含 $4$ 位数字，且存在回文排列 $2442$。

给定一个正整数 $s$，求小于 $s$ 的最大优美数。

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.

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$）—— 你需要解决的测试用例数量。

接下来是 $t$ 行，每行代表一个测试用例，包含一个字符串，该字符串为数字 $s$ 的十进制表示。保证该字符串长度为偶数、不含前导零，且存在至少一个小于 $s$ 的优美数（beautiful number）。

所有测试用例中 $s$ 的字符串长度之和不超过 $2 \cdot 10^5$。

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

对于每个测试用例，输出一行，包含小于 $s$ 的最大优美数（保证答案存在）。