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
meher_24: 2020-05-07 16:17:01

do i just increment the input by one and check if its a palindrome or is there a better and a faster method?

hritik_1105: 2020-05-07 06:23:05

Its logic is easy but implementation is hard.
It took me one complete day to make logic that covers all cases and then AC in 1 go.

bernard_mocko1: 2020-05-04 01:09:54

When they say, that elements are not more than 1000000 digits, they are not joking, my char array in C was one element to short

Last edit: 2020-05-04 01:17:10
fawad: 2020-04-25 09:54:46

guys, there is space character after input in every line, just take care of it

harsh_11: 2020-04-19 10:53:17

I am getting wrong answer for my submission, i am unable to figure out why, my code is working fine for the other listed test cases (the ones that are being provided by others in comment section) and it's also working fine for the a large no like 99999999999999

Last edit: 2020-04-19 10:57:50
trulyness: 2020-04-17 20:31:20

here are the test cases on which your code should work:

123456
1234567
9999
99999
1
2991
3994
9999
5448
65343454
100
4111

A tip for debugging in case you get wrong answer and are not sure where your code is failing:

- use a correct code and run it for all numbers from 0 to 100000 and use your code and run it for all numbers from 0 to 100000. check the difference in the outputs and you'll find which test cases are failing.

hope this helps!

Last edit: 2020-04-17 20:35:17
arpit_jc21: 2020-04-14 12:47:31

i dont understand whats the problem here....my code gives correct answer in ideone...but it shows WA in here.

the_nine_tail: 2020-04-13 08:10:35

The same code got accepted at CodeChef, but throws WA in Spoj. Didn't get it... is there any problem with Spoj compiler???

g10van1: 2020-04-10 22:57:01

My code in Python 3 and C# resulted ' time limit exceeded', but in C++ it's accepted.

mahatejvarma: 2020-03-21 13:46:34

Accepted after 2 hours!!!


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