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
wille_25: 2021-01-08 20:58:32

Finally AC --- (0.02s)
The Input given by shreyas_07 is not working correctly (infinite loop occurs in c++),
But it Still Got AC ;

sher_007: 2021-01-07 11:27:04

I used string to take input as the input can be as large as 10^6 digits and then i stored it in an int array.
It is giving correct answers but I got TLE on the problem. Any suggestions as to how approach this problem in much optimized way??

satyam552000: 2021-01-07 09:12:22

check for 9 and 99 and use strings it worked for me

shreyasz_07: 2020-11-23 17:45:18

I'm getting tle

Last edit: 2020-11-23 17:47:56
xander_70: 2020-11-16 09:57:10

How could I fix my TLE problem

shreyas_07: 2020-11-15 09:28:17

If you're getting wrong ans use these tc's:

TC :
40
808
2133
9999999
999999
899998
3423355356
100001
46887767
9
99
0
1991
1239400
123999500
56442
56471
123456
1234567
77777777777
2991
3994
9999
5448
653434
101
199
0012100
0003
123456
1234567
9999
99999
1
2991
3994
9999
5448
65343454
100
4111


Ans :

818
2222
10000001
1000001
900009
3423443243
101101
46888864
11
101
1
2002
1240421
124000421
56465
56565
124421
1235321
77777877777
2992
4004
10001
5555
654456
111
202
0013100
0110
124421
1235321
10001
100001
2
2992
4004
10001
5555
65344356
101
4114


Sorry some values might be repeated.
I got AC after 3 hrs of trying..

rajutsav1234: 2020-11-06 19:44:38

i have been writing code in C and it works perfectly on Ideone and is giving correct output, but here I am getting error. It is showing wrong answer. Please help me...

bong0s_guy01: 2020-10-25 06:53:04

Hey, does anyone know where can I get the input tests cuz I've tried the most optimal code I could but still exceed time limit, so I just want to k now where can I get the test to know how to optimize it

vcillusion: 2020-10-18 13:00:47

In C#, I tried with BigInteger and without it, the result is TLE. Can it be a limitation for C#? Please fine my solution below
http://discuss.spoj.com/t/palin-the-next-palindrome-time-limit-exceeded/40347

coder582: 2020-10-08 09:16:28

All the peeps who say that there solution is correct but they are getting WA, trust me, your solution is wrong.
Now to identify the test cases where your solution goes wrong, try to write a code that solves the problem for numbers <= 10000 (this will be enough, I guess. solution can be easily found by incrementing this number till you get a palindrome), now use STRESS TEST with this solution and your original code, you will get the Test Cases that you need to take care of. (For Stress Test you can visit Errichto's YouTube channel).
Hope This Helps!


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