SCUSA Region ICPC Masthead ACM Balloon Logo
2014 ACM ICPC South Central USA Regional Programming Contest

5 - Palindrome Numbers

Palindrome Numbers

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.


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


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


Sample Output