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
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!!!

atulav: 2020-01-12 12:10:03

Finally did it after years.

sayan_244: 2019-12-19 07:11:03

LOL! can the input number have leading zeroes??
I am having a hard time getting rid of them.... :/

ashwanitr001: 2019-12-01 12:14:56

For people getting WA try test cases like 0,99,199
The outputs should be 1,101,202 respectively

harindra2002: 2019-11-23 14:10:06

should we input the values given in the example or leave the input to the computer?

aneeshs_7901: 2019-11-19 16:19:14

its giving wrong answer everytime i submit.its working fine and the output is correct in ideone

binit_54: 2019-10-15 06:22:42

can someone give me some idea on how to store the strings in this problem for later access when all the input has been finished?

pranay19263: 2019-10-10 08:19:56

giving runtime error all the time
beside it is fully working on ideone


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