{"raw_statement":[{"iden":"statement","content":"_Yes, that's another problem with definition of \"beautiful\" numbers_.\n\nLet'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.\n\nGiven a positive integer _s_, find the largest beautiful number which is less than _s_."},{"iden":"input","content":"The first line contains one integer _t_ (1 ≤ _t_ ≤ 105) — the number of testcases you have to solve.\n\nThen _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_.\n\nThe sum of lengths of _s_ over all testcases doesn't exceed 2·105."},{"iden":"output","content":"For each testcase print one line containing the largest beautiful number which is less than _s_ (it is guaranteed that the answer exists)."},{"iden":"example","content":"Input\n\n4\n89\n88\n1000\n28923845\n\nOutput\n\n88\n77\n99\n28923839"}],"translated_statement":[{"iden":"statement","content":"_是的，这是另一个关于“美丽”数字定义的问题_。\n\n我们称一个正整数 #cf_span[x] 为 _美丽的_，如果它的十进制表示（不含前导零）包含偶数个数字，并且存在一种对该表示的排列，使其成为回文。例如，#cf_span[4242] 是一个美丽的数字，因为它包含 #cf_span[4] 个数字，并且存在一个回文排列 #cf_span[2442]。\n\n给定一个正整数 #cf_span[s]，找出小于 #cf_span[s] 的最大的美丽数字。\n\n第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 105]) —— 表示你需要解决的测试用例数量。\n\n接下来 #cf_span[t] 行，每行代表一个测试用例，包含一个字符串，该字符串是数字 #cf_span[s] 的十进制表示。保证该字符串具有偶数长度，不含前导零，且至少存在一个小于 #cf_span[s] 的美丽数字。\n\n所有测试用例中 #cf_span[s] 的长度总和不超过 #cf_span[2·105]。\n\n对于每个测试用例，输出一行，包含小于 #cf_span[s] 的最大的美丽数字（保证答案存在）。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 105]) —— 表示你需要解决的测试用例数量。接下来 #cf_span[t] 行，每行代表一个测试用例，包含一个字符串，该字符串是数字 #cf_span[s] 的十进制表示。保证该字符串具有偶数长度，不含前导零，且至少存在一个小于 #cf_span[s] 的美丽数字。所有测试用例中 #cf_span[s] 的长度总和不超过 #cf_span[2·105]。"},{"iden":"output","content":"对于每个测试用例，输出一行，包含小于 #cf_span[s] 的最大的美丽数字（保证答案存在）。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in \\mathbb{Z}^+ $ be a positive integer with even decimal length and no leading zeros.  \nA number $ x \\in \\mathbb{Z}^+ $ is *beautiful* if:  \n- Its decimal representation has even length and no leading zeros.  \n- There exists a permutation of its digits that forms a palindrome.  \n\n**Constraints**  \n1. $ 1 \\le t \\le 10^5 $  \n2. For each test case, $ s $ is given as a string of even length $ \\ell \\ge 2 $, with no leading zeros.  \n3. The sum of all $ \\ell $ over test cases $ \\le 2 \\cdot 10^5 $.  \n4. There exists at least one beautiful number $ < s $.  \n\n**Objective**  \nFor each test case, find the largest beautiful number $ x < s $.","simple_statement":null,"has_page_source":false}