PALIN - The Next Palindrome

no tags 

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 Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6

hide comments
PrasadG: 2015-07-29 18:46:27

Finally got green..
For WA guys..check following test cases->
909 --> 919
99899 --> 99999
9989 --> 9999
99999 --> 100001

Last edit: 2015-07-29 18:47:17
luisdanielmesa: 2015-07-25 06:56:49

I'm done... the checker is wrong.

Last edit: 2015-07-25 07:35:47
luisdanielmesa: 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...

khanhmg: 2015-07-23 07:05:56

Can I take char array as input?

dheerajm: 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??

spinwheel_00: 2015-07-18 09:20:21

finally got green AC after a week of volunteer works. It's so exciting. :)

yhunroh: 2015-07-18 07:32:39

the output shouldn't have new line at last.
i've got 5 WA cause of that

amidesr: 2015-07-17 20:11:26

I wrote the code for these exercise in python. Always gave me Time Exceeded. This is for python??.
http://ideone.com/NdK5Vo

ammyraj_1993: 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

Livewire: 2015-07-11 20:47:42

:D Got AC in 2nd attempt!


Problem's scores 1 vote

Concept difficulty
Concept difficulty 41%
Implementation difficulty
Implementation difficulty 44%
55 1