For a given positive integer M, write the value of the smallest palindrome larger than M to output.

Note : Leading zeros are not the part of the numbers.

Note : What is a pallindrome ? Well, that's a subtask for you. Find it out yourself if you don't know.

Input

The first line contains integer t, the number of test cases. Integers m are given in the next t lines.

Output

For each m, output the smallest palindrome larger than m.