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
mrzydeco: 2018-07-08 06:38:12

The hapless solver of this solver of this problem might have quite reasonably assumed that the input would consist only of digits and newline characters. If you're going to allow stray whitespace at the beginning or end of input lines, that should be mentioned in the input specification.

It really is silly that we have to GUESS this sort of detail IN THE DARK. This flaw seriously vitiates the quality of an otherwise really good problem.

Last edit: 2018-07-09 00:00:50
piyushonkar: 2018-07-02 09:40:38

It is showing correct output for 99 and 999. But when I submit the solutuion it says wrong answer. Can someone post the good test cases? Thank You in advance.

wrzoboo: 2018-06-22 16:44:31

@badman98 you want to avoid using int(hugenumber) and try the approach of int(hugenumber[-1]), think about how addition works in principle, replacing some substring (of length much lower than the entire string which shortens the execution) with some other substring. I hope you'll figure this out :).
example:
100+1 means look at last digit of 100 and change it to the next digit (0 -> 1 in this case)
watch out for '9' being that last digit though ;)

badman98: 2018-06-15 11:32:51

@wrzoboo what do u mean by writing own custom function to add 1 how else we can do it without converting string to integer

kieukhanhmta: 2018-06-10 08:38:06

Hi all!
I wrote by C#.
I ran it on Visual and ideone.com was correct.
But in here, it was runtime error NZEC
Please Help me.

sonuexpc: 2018-06-09 14:45:21

AC in second go...

no_name_123: 2018-06-05 21:50:39

esf

Simes: 2018-05-31 07:54:21

@vritta and @vivek_dwivedi - I tested whether there are any numbers with a leading zero, and there aren't any, not even zero itself.

vritta: 2018-05-31 06:19:02

Thanks Vivek, have been stuck on that problem for days. Now I know it's their fault.

vivek_dwivedi: 2018-05-30 04:40:06

very good problem ! total shit test cases even admin don't know that 0 is not a positive no.
and how the answer for 000 can be 010 it should be 1 wasted a lot of time . Totally frustrating


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%
458 16