PALIN - The Next Palindrome

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. Integers K are given in the next t lines.

Output

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

Example

Input:
2
808
2133

Output:
818
2222

Warning: large Input/Output data, be careful with certain languages


Added by:adrian
Date:2004-05-01
Time limit:2s-9s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6

hide comments
2015-07-25 06:33:26
I'm pretty sure this problem is not being checked right in java... After 10 attempts I checked with 100 Strings against a code that was accepted... and both produce the same results... but mine is still rejected...
2015-07-23 07:05:56
Can I take char array as input?
2015-07-22 09:37:13
With the same code, I am getting write answer in codechef judge , where as this judge is giving me wrong answer. Can anyone explain me what's happening here pls??
2015-07-18 09:20:21
finally got green AC after a week of volunteer works. It's so exciting. :)
2015-07-18 07:32:39
the output shouldn't have new line at last.
i've got 5 WA cause of that
2015-07-17 20:11:26
I wrote the code for these exercise in python. Always gave me Time Exceeded. This is for python??.
<snip>


Last edit: 2023-01-30 20:32:13
2015-07-16 15:41:18
PALIN in my compiller it is executed u give so many large number it does care but here wrong answer coming.what the fuck is this
2015-07-11 20:47:42 Livewire
:D Got AC in 2nd attempt!
2015-07-11 01:58:55 Abhishek Prasad
14643636.. can anyone please suggest me what did I do wrong here?
2015-07-10 07:18:39 poojan
giving me wrong ans :
i take care of :
1->0 to 8-> digit+1
2->9,99,999,9999->11,101,1001.10001
3->405,504->414,505
4->998,989->999,999
5->421999767->422000224
6->100->101
still getting wrong ans plz help! lots of wrong ans for this and problem statment is very bad! not clear about single digit.
cheak my code id is : 14637932

Last edit: 2015-07-10 08:15:07
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.