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
satyamr1: 2017-02-23 14:02:07

How to store such a large number with 1000000 digits?

primecode: 2017-02-21 08:56:58

#saurabh your last two outputs are wrong. it must be 101 and 1001.

bansalrajat20: 2017-02-14 19:55:47

why i am getting TLE error

rohit9934: 2017-02-10 16:50:34

Can anyone tell me what will happen fo test case 1,2,3.....9. and more test cases please

nilabja16180: 2017-02-09 10:32:31

Problem statement says, output numbers should be without leading zeroes?

piyushmittal: 2017-02-02 14:30:20

I think question is wrong,because my friend gets AC but According to his
intput
00000
0000
0011
output
00100
0110
0110

sachinsharma12: 2017-02-02 12:22:11

Yippi
Ac in one go..

abhishek1singh: 2017-02-01 12:40:40

Code running well in my compiler but here it isn't..Can i see Test Cases??

Last edit: 2017-02-01 12:41:13
Fodor Gabor: 2017-01-29 15:37:31

For those encountering TLE in Python (despite otherwise good solution):
- str( int(number) +1) is VERY slow, causing TLE (or similar string to int to string conversions) -> use string manipulations instead
- ''.join(reversed(astring)) VS astring[::-1]: the first option is (about 10x) slower, but for this problem, either way is fine (it is NOT the reason for your timeout)

Last edit: 2017-01-29 15:42:40
anveshchava: 2017-01-13 13:41:16

Code running well in my compiler but here it isn't..Can i see Test Cases??


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 38%
Implementation difficulty
Implementation difficulty 48%
194 6