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

vritta: 2018-05-29 06:55:16

Last edit: 2018-05-29 10:31:39
baddu609: 2018-05-27 14:44:10

Check Output for 99 and 999 also! They can be the border case if logic was similar to mine.

wrzoboo: 2018-05-24 17:00:16

I can't believe how people managed to do 0.04s in Python3. Through hard fought battle I finally managed to get AC but my time is 3.5s. Any tips on how they might've done it? (inb4 "just optimization LOL")

For Pythoners to avoid TLE:
treat input lines only as strings, dont convert them to anything - int(input) + 1 ====> TLE
for operations on input lines write your own cust functions that do not use conversion (so int(input) + 1 is replaced by customFuncPlus1(input))
last line of input doesnt have newline symbol while all others have, use strip() for inputs - costed me one WA

ashisha690: 2018-05-22 09:40:03

@ayushtopper string

Last edit: 2018-05-22 09:44:21
ayushtopper: 2018-05-21 09:52:35

Since input can be very very large like 13413515134000000000000000013488097081324
so how to take input in cpp? Anybody which datatype you used?

cabbie: 2018-05-18 02:06:13

Spent so much time on this. But finally got it :)

adityamudgil: 2018-05-10 19:22:27

Last edit: 2018-06-03 16:15:40
linearspam: 2018-05-06 22:54:09

difficult life lesson: remove printf debugging before submitting...

chibaku_tensei: 2018-04-21 16:31:52

Why is the Integer 2 not also an Palindrome ?


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