← 返回题目列表

Codeforces · 946/E

E. 最大的美丽数字

中文机器翻译题面 查看原题

是的,这是“美丽”数字定义的另一个问题。

如果一个正整数 x 不带前导零的十进制表示包含偶数个数字,并且存在该表示的回文排列,那么我们称其为美丽的。例如,4242 是一个美丽的数字,因为它包含 4 位数字,并且存在回文排列 2442。

给定一个正整数 s,找到小于 s 的最大美丽数。

输入

第一行包含一个整数 t (1 ≤ t ≤ 105) — 您必须解决的测试用例的数量。

接下来是 t 行,每一行代表一个测试用例并包含一个字符串,该字符串是数字 s 的十进制表示。保证该字符串长度为偶数,不包含前导零,并且至少存在一个小于 s 的漂亮数字。

所有测试用例的 s 长度总和不超过 2·105。

输出

对于每个测试用例,打印一行包含小于 s 的最大美丽数字(保证答案存在)。

示例

输入 #1

4
89
88
1000
28923845

输出 #1

88
77
99
28923839