
ZOJ Problem Set  3816
A number that will be the same when it is written forwards or backwards is known as a palindromic number. For example, 1234321 is a palindromic number. We call a number generalized palindromic number, if after merging all the consecutive same digits, the resulting number is a palindromic number. For example, 122111 is a generalized palindromic number. Because after merging, 122111 turns into 121 which is a palindromic number. Now you are given a positive integer N, please find the largest generalized palindromic number less than N. InputThere are multiple test cases. The first line of input contains an integer T (about 5000) indicating the number of test cases. For each test case: There is only one integer N (1 <= N <= 10^{18}). OutputFor each test case, output the largest generalized palindromic number less than N. Sample Input4 12 123 1224 1122 Sample Output11 121 1221 1121 Author: LIN, Xi Source: The 2014 ACMICPC Asia Mudanjiang Regional First Round 