{"problem":{"name":"E. Largest Beautiful Number","description":{"content":"_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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF946E"},"statements":[{"statement_type":"Markdown","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_.\n\n## Input\n\nThe 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.\n\n## Output\n\nFor each testcase print one line containing the largest beautiful number which is less than _s_ (it is guaranteed that the answer exists).\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","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] 的最大的美丽数字（保证答案存在）。\n\n## Input\n\n第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 105]) —— 表示你需要解决的测试用例数量。接下来 #cf_span[t] 行，每行代表一个测试用例，包含一个字符串，该字符串是数字 #cf_span[s] 的十进制表示。保证该字符串具有偶数长度，不含前导零，且至少存在一个小于 #cf_span[s] 的美丽数字。所有测试用例中 #cf_span[s] 的长度总和不超过 #cf_span[2·105]。\n\n## Output\n\n对于每个测试用例，输出一行，包含小于 #cf_span[s] 的最大的美丽数字（保证答案存在）。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF946E","tags":["greedy","implementation"],"sample_group":[["4\n89\n88\n1000\n28923845","88\n77\n99\n28923839"]],"created_at":"2026-03-03 11:00:39"}}