2 shunfurh shunfurh 于 2017.08.28 09:04 提问

Generalized Palindromic Number

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.

Input

There 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 <= 1018).

Output

For each test case, output the largest generalized palindromic number less than N.

Sample Input

4
12
123
1224
1122
Sample Output

11
121
1221
1121

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.11 23:43
已采纳
Csdn user default icon
上传中...
上传图片
插入图片