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
cegprakash: 2014-01-15 15:17:31

Martijn Muijsers: true that

2
9994
99994

should produce

9999
99999

But my ACC code produces
10001
100001

Jatin Singla also specified that he got ACC when his code produced 1111 for 1991 where it should produce 2002.

Sachin Sai Krishna's code produces 9 for 9 and got ACC.

Test cases are weak. It's been 9 years. But it's okay to rejudge after making the test cases strong.

Aravind Sagar: 2014-01-15 15:17:31

@shweta choudhary The problem is that the input number can have 1000000 digits, so int and long long won't work. Try to store it as a string and think of a different approach.

aqua: 2014-01-15 15:17:31

checked all cases still getting WA ...can anyone help? i am coding in C... http://ideone.com/G3Ept4 even getting correct output here

Last edit: 2013-12-18 21:07:23
amin ababneh: 2014-01-15 15:17:31

omg!!!! same code i wrote in java and c++
java gave me tle then rte . c++ worked just fine is that possible or i did something wrong while transforming the code from one lang to another ?

Martijn Muijsers: 2014-01-15 15:17:31

Great problem, but some wrong answers appear to be accepted? :P

Shashank Gupta: 2014-01-15 15:17:31

Good problem. Just be very careful with what functions/operations you use in your language. Even in slower languages, this problem is easy to do with the high time limit.

Sachin Sai Krishna M: 2014-01-15 15:17:31

for 9 the ans should be 11 but if even 9 gets printed u can get AC:) pls check that one

Gaurav Mishra: 2014-01-15 15:17:31

To much hard coding :(

ISHANI: 2014-01-15 15:17:31

GREEN LINE after hard hard coding
but really VERY VERY NICE LOGIC

Abhash Singh: 2014-01-15 15:17:31

3.5 hrs straight into this one!
AC in first attempt!
no points!what is this! :(


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