next palindrome number

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



Response1:
If ( (number already a palindrome) or (right half <> left half)
___ Copy reverse of left half to right half.


Response2:
perfect..above soln always gives correct answer.

for even no.of digits join n/2,n/2+1 th digit as one digit(so that u've to increment both these digits for 1st case).
ex.1441
ans->> 1551(if i'm not wrong)
here both the digits(2nd ,3rd).
this may also be done using naive approach like

while(!ispalindrome(++n))
;
output(n)

but this consumes a lot computing time.u can verify this
by giving large nos as i/p.


Response3:
the solution is not correct...
consider the case say 323421
now the right half ie 421 is greater than left 323
so according to your algo the answer wud be 323323
which is wrong...

the correct algo is
If ( (number already a palindrome) or (right half <> left half)
___increment the last digit of left half by 1 and copy the reverse of it to right half.



Response4:
>> In case of even length.. middle element is the rightmost element of left half.
>> otherwise middle element is separate from left half.

So, the correct algo goes like..

If( reverse left half> right half )
___ Copy reverse left half to right half
else
___ Increment middle element by 1 and then Copy reverse left half to right half.



Response5:
Modified algo

For even digits
increment left half until left half
copy left half to right half