是的,这是“美丽”数字定义的另一个问题。
如果一个正整数 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