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

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 ?

David Winiecki: 2018-04-09 08:10:24

Don't assume every line ends in a newline. I had to add logic like "if last character of input read from this line is not a number, then remove it (decrement length), else do nothing (don't decrement length)". Took me a very long time to figure that out. Extremely frustrating. :/

ashutoshiiita: 2018-03-30 18:04:55

TLE on using boost library of C++ why??

prabhakar2050: 2018-03-27 13:32:57

@Piotrek Nicowski Thanks :D

Piotrek Nicowski: 2018-03-23 20:39:46

@prabhakar2050 - For each K, output the smallest palindrome *** LARGER THAN *** K.


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