Largest Beautiful Number

题意翻译

【题目描述】 如果一个正整数在十进制表示法下，不含前导零，有偶数个数字，并且对于它的所有数字来说，有一种排列方式使得这些数字组成一个回文数，那么这个数就是“美丽数”。例如4242是一个美丽数，因为它含有4个数字，这4个数字可以组成一个回文数2442。 给定一个正整数s，求严格小于s的最大美丽数。 【输入格式】 第1行，1个整数t，表示数据组数。 下面t行，每行1个十进制数s。 【输出格式】 对于每个s，输出严格小于s的最大美丽数。 数据保证有解。 【数据范围】 t <= 10^5 s的长度<= 2*10^5 感谢@刷题永动机 提供的翻译

题目描述

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 $ .

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1<=t<=10^{5} $ ) — 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·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).

输入输出样例

输入样例 #1

4
89
88
1000
28923845

输出样例 #1

88
77
99
28923839