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


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

hide comments
2018-12-12 07:25:17
I'm getting runtime error NZEC in this problem while submitting
but perfectly running on ideone platform

Last edit: 2018-12-12 07:26:02
2018-12-10 22:54:24
This is a nice problem.....Try to consider all the cases........Not a easy problem so don't worry it will take some time to solve...try to optimize your code....
For WA try to consider boundary cases and u may consider some of the test cases given in comment section.
2018-12-08 09:39:37
Anyone please help me.
I tried many times by taking the number as int .i am also done with the test case starting with 0 i.e i am taking 010 as 10.Though it is showing wrong answer every time. i am getting correct answer in my compiler.

Last edit: 2018-12-08 09:41:33
2018-12-08 08:27:27
@ahnaf97: there will be no such input with leading zeroes.
eg: 00091 will be considered as 91.

Last edit: 2018-12-08 08:29:55
2018-11-19 09:07:05
i tried every possible case...but still WA. NEED HELP!!!
if input is - 010 , 000 what is the output?
11, 1 ?
2018-11-15 10:12:53
@abhinav_12716 we need to find next smallest palindrome
2018-11-15 08:15:20
808 is a pallindrome itself
2018-11-14 10:55:14
SIGABRT runtime error how to resolve it? my program is working fine in other ide here its showing error.
2018-11-06 15:16:20
@omar_elbzt_96 when your program use too much "if" then your time to run the program will be exceeded. It is similar to when you do your exam and you run out of time.
2018-11-04 13:33:13
Someone knows what the problem is when we have " TIME LIMITE EXCEEDED" while in the program there is no mistake.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.