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
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!
2020-09-09 19:26:45
be careful with "K is not more than 10^6 digits", so you can't use long long type to store the number.
Also, TLE may because it try too many times.

Last edit: 2020-09-09 19:28:13
2020-08-25 21:13:02
I'm getting SIGABRT,even though it is working successfully on ideone.
2020-08-20 10:19:07
If you get "wrong answer", try to make you own comprehensive test suite: iterate from 0 to some large n, if n is a palindrome, your function must return it as a result for all the numbers from previous palindrome to n.
2020-08-16 17:45:08 Shahin Ram Krishna
any guidelines on how to use cin and cout for SPOJ? my testcases are producing correct result. all the corner cases are checked but spoj throws wrong answer. can someone tell do I need to flush the stdin/stdout ?

Last edit: 2020-08-16 17:46:00
2020-07-28 22:20:28
My code is all correct and working in ide but here it is exceeding time limit
2020-07-23 21:17:07
WTF!!! my code is working fine with my ide (also tried online compiler) this SPOJ submission is fu$%*#@^&ing

Last edit: 2020-07-23 21:21:35
2020-07-16 08:47:07
k is not <= 1000000
use string to store and modify the value
2020-06-25 20:54:32
i think this is the worst platform i've ever came across.
my most of the source codes even being correct are validated as wrong by the SPOJ judge.

[NG]: Breaking news: if the solution is validated as wrong, it's not correct.

Last edit: 2020-06-26 05:53:18
2020-06-15 17:35:11 Ankur Jain
If you're using Java don't use BigInteger for airthmatic operations else it'll raise NZEC or TLE exceptions.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.