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
