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


hide comments
quock: 2018-01-23 08:19:38

Here description say K can not be larger than 1000000 but the test cases assert also a big int
11111111111111111111211111111111111111111. Is it expecting case to cover ?

hrk27071999: 2018-01-15 19:39:46

can someone give me corner cases for this code that is easy to mistake?

jonmanu: 2018-01-15 19:18:32

I got TLE in this program. How should i fix this?

bashnewbie: 2018-01-08 15:34:46

Nice problem ;)

If you analyse well enough you will find that there are many corner cases that will take care of themselves

anna_9701: 2018-01-07 12:18:31

akash9827 Long int is too short to handle such long number as ~1000000 digits...

akash9827: 2018-01-06 05:32:10

I did this by reversing the number , i've checked corner cases too , all are correct.
but then too i'm getting wrong answer.
NOTE---->>> I've taken input as "unsigned long int", do i need to take input as a string and then do the processing??

mona_coder: 2017-12-28 11:56:16

integer K of not more than 1000000 digits; why it is showing wrong answer?

pust_coder: 2017-12-28 11:04:14

what is wrong of this problem??please ans me,,
<snip>

Last edit: 2022-07-26 22:16:48
nadstratosfer: 2017-12-23 23:55:15

TL is very lenient by SPOJ standards, and friendly for slower languages. I even got AC with a hastily put together semi-bruteforce in 3.45s while a proper solution took 0.05s. Good problem for beginners to learn about efficiency of very common operations and pick up some good practices.

ystm: 2017-12-22 17:01:36

I wrote same algorithm in python and rust, but only rust passed. If you've got TLE in slow language, consider to choose another faster one.


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

Problem's scores 1 vote

Concept difficulty
Concept difficulty 37%
Implementation difficulty
Implementation difficulty 50%
467 16