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

Neeraj Jain: 2017-04-22 19:14:52

Getting `runtime error (NZEC)`, All Test Cases working fine , even which @piyush1339 mentioned, if anyone can help.

nput:
5
9
100
999
4998
421999767

Output:
6
11
101
1001
5005
422000224

rubel_cs: 2017-04-17 11:42:39

Though my code passed every test cases in comment section still getting wrong answer :(

alim97: 2017-04-07 15:16:16

It's funny. I submitted my own code that was accepted last time. And now it gives Wrong answer :D

masterbios: 2017-04-02 22:59:12

if you got NZEC in java simply use
public static void main(String args[])throws java.lang.Exception
{}

rachit690: 2017-04-01 16:09:40

Pls check my code, its giving write answer for all test cases i run, still i get WA

shubha_096: 2017-03-31 06:40:31

where my code lacks?

Juan: 2017-03-26 03:40:18

@satyamr1 I'm trying to solve it keeping the string representation of the number and building the next palindrome by string manipulation. I won't give more details, because it would simply give too much information


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%
468 16