A word is considered a palindrome if it is the same when read left to right or right to left. For this problem, a positive integer is considered a palindrome if its base 10 (decimal) representation is the same from left to right as right to left. For each number, determine the smallest palindrome by value that is greater than or equal to that number. Unlike with Nascar car numbers, leading zeroes are insignificant and do not appear in any number in the input or output of this problem.

Input

The first line of input will contain the number of test cases, $T$ ($1 \leq T \leq 50$). Each of the following $T$ lines contains a positive integer $N$ that is no more than $80$ digits in length.

Output

The output of each test case will be a single line containing the smallest palindrome that is greater than or equal to the input number.

Sample Input

2
42
321

Sample Output

44
323