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
horizon121: 2017-05-19 22:57:25

Really Nice problem.Initially I didnt see the limits so I got a WA then got ac :D....These problems does increase your knowledge..All those applying Brute Force..Don't

mishra10: 2017-05-19 16:56:37

using \b in case of 99 or similar type...After removing this VOILA...Cheers.....

nawaz_ra: 2017-05-18 20:47:21

My solution is running fine when executed in ideone.com but here it is throwing time limit exceed error!!
any advice?

ellucion: 2017-05-16 01:08:22


I'm using Java, and even my program passing on several tests already done by me, and even using the examples of the comments found here, he from NZEC, does anyone help?

arroz14: 2017-05-13 16:35:16

my code is passing all the test cases on ideone ; still getting wrong answer here

jayeshd: 2017-05-09 18:27:40

For guys who are solving the question in python don't try to convert the integer to string, as in python it is very costly operation. Try to solve the problem by keeping the number in string and you should be good to go.

for people struggling with wrong answer -
try these test cases -
0
9
99
999
9999
101
11
100000

answer should be
1
11
101
1001
10001
111
22
100001

Kaushik Mitra: 2017-05-08 15:49:37

This problem is awesome!! 5 hours straight into it and then the GREEN light. Loved the problem.

hkuadithya: 2017-05-02 06:46:16

Easy problem. A few tips for folks who are stuck.
After reading the String, you can store the data in an integer array. For example you can store char '0' as 0 in int array.
I found this might make arithmetic operations easier than using char array.

Finally, 1,000,000 Digits imply that the maximum number is in the order of 10^(1,000,000). No int datatype can store this, so use char array.

Please note:
1 => 2
9 => 11
99 => 101

@narutohokage_1 thanks for your test cases. Check each of these outputs.

Input :
12345
14325
12325
52321
12945
12925
99998
99999
98999
89999
231
132
268545813
208545813
2862
2682
2221
1222
2993


o/p
12421
14341
12421
52325
13031
13031
99999
100001
99099
90009
232
141
268545862
208555802
2882
2772
2222
1331
3003

Last edit: 2017-05-02 06:48:54
lpbove: 2017-05-02 02:51:20

I've been looking through the comments and I've yet to find a case in which my program fails.
I'm getting NZEC error at the judging phase though.

boyue: 2017-04-23 12:26:12

wrong answer too, even passed every test case...
someone can help:((


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%
217 6