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
bigbrobd: 2017-12-21 22:28:48

Following test cases r correct..
Still says wrong answer.. I cant understand what is happening.

Input :
22
19091919191
1999991
121
100
890
1221
123450000004
0
808
2133
11111111111111111111
11111111111111111111111111111111111111111
1119191991900234245239919234772376189636415308431
99
999999
241342191
374294242
242343242
898
77777
888888
13413515134000000000000000013488097081324

Output :
19092029091
2000002
131
101
898
1331
123450054321
1
818
2222
11111111122111111111
11111111111111111111211111111111111111111
1119191991900234245239920299325424320091991919111
101
1000001
241343142
374303473
242353242
909
77877
889988
13413515134000000000100000000043151531431

Last edit: 2017-12-21 22:29:24
snitesh24: 2017-12-13 20:14:48

Accepted after passing below testcases..
Input :
22
19091919191
1999991
121
100
890
1221
123450000004
0
808
2133
11111111111111111111
11111111111111111111111111111111111111111
1119191991900234245239919234772376189636415308431
99
999999
241342191
374294242
242343242
898
77777
888888
13413515134000000000000000013488097081324

Output :
19092029091
2000002
131
101
898
1331
123450054321
1
818
2222
11111111122111111111
11111111111111111111211111111111111111111
1119191991900234245239920299325424320091991919111
101
1000001
241343142
374303473
242353242
909
77877
889988
13413515134000000000100000000043151531431

aar_em: 2017-12-12 14:19:41

It works for manually entered inputs, why does it show here wrong answer?

saikumarm4: 2017-12-05 14:33:45

how does Wrong answer is decided ? Does it consider time and space complexity also ? or only after looking at the test cases ?@prothlete even I am facing same issue, did you by any chance resolved it ? it works in my IDE and fails online

Last edit: 2017-12-05 17:31:11
code_killerx: 2017-12-04 06:28:56

Getting a WA in this code don't know why pls help https://ideone.com/4t9xJa

techventer_936: 2017-11-30 23:55:21

consider special cases and for all other logic is same.
go for mirror image from mid point.
:)

w1583236: 2017-11-29 06:31:57

what about 19199192

coolbudy1998: 2017-11-24 16:46:21

Please provide a sample of a number with 53435 digits...i think my whole computer screen will fill away. Is the language given in prob statement is wrong?? 1000000 digits should be replaced with only 1000000. Isn't it?

dsr: 2017-11-19 21:30:23

Why am I getting NZEC for python :'(

prothlete: 2017-11-18 17:52:17

in my ide, i get the correct answer against every possible test case, but here, why does it show wrong answer?


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