A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input

The first line contains integer t, the number of test cases. Followed by t lines containing integers K.

Output

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

Example

Input:

2

808

2133

Output:

818

2222

solution:

def compare(value):

value = value[::-1]

return value

T = int(input())

for _ in range(T):

k = int(input())

flag = 1

increase = k+1

while flag == 1:

if str(increase) == compare(str(increase)):

print(increase)

break

else:

increase += 1