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
dimz01: 2016-12-07 08:15:38

Thanks @dusan_1989 for test case. Test case with number 9 is super effective :)

nitish_garg503: 2016-12-06 20:42:15

why i always get wrong answer error on this site.
doing coding from 10 years and finish almost all websites questions.....

glasses: 2016-12-04 03:32:27

Thanks @vector1996 for test cases:)

pratyush2311: 2016-12-01 13:19:19

Great problem. Learned a lot. Must try for beginners :D

dusan_1989: 2016-12-01 02:59:36

People always test for number 9. In my case, code was good for 99,999,99999,99999, but when i finally try to input 9, ouput was 10 ,so i solve that problem, and now is accepted. Other thing i want to say to you ,that i found solution for this problem only when i put numbers on paper, and tried to find solution mathematical. Just think in that way, and you are on the right path.

cnexans: 2016-11-29 16:51:01

@sw3110 If it's slow, it might be wrong. Keep trying!

m_ashutosh: 2016-11-15 12:38:46

what does it mean from "not more than 1000000 digits"? Do you mean no. of digits of the number is not more than 10^6 or the number is not greater than 10^6??

sunilkumarc: 2016-11-15 12:38:27

I'm also facing the same issue many people are facing here with Python. I'm sure I have efficient solution. But getting time limit exceeded.

chaudhary95: 2016-11-14 10:08:38

I am not able to find error

[code snipped]

Last edit: 2016-11-14 10:21:00
sw3110: 2016-11-08 03:04:14

Is there something wrong is using Python 3.4. I am absolutely sure that I have an efficient solution(not loops etc) but I am always getting time limit exceeded. Any help is greatly appreciated.


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

Problem's scores 1 vote

Concept difficulty
Concept difficulty 39%
Implementation difficulty
Implementation difficulty 48%
171 6