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
2015-05-08 09:24:10 ash
getting TLE for a large string of random numbers :( whereas correct answer for short strings of random numbers and answer is also coming correct if all the characters in the string are 9's (no matter what the length of the string is )...plz help...
2015-05-07 13:10:46 AbuGasem
<snip>
This Is My Code Whats Wrong ????

Last edit: 2022-07-26 22:29:38
2015-05-05 23:42:27
@adrian: Can you let me know which test this is <snip>

Last edit: 2022-07-26 22:29:34
2015-05-04 19:36:08 sksuman.nitw
finally accepted.....
points to remember
1. check for all 9's i.e for 9999 output should be 10001
2. check for palindrome no.
3. palindrome of single digit is its next digit. i.e 0--->1, 5--->6, 3->4 and for 9--->11
4. some test cases
1 2 9 2 1 ----------> 13031
7 8 3 3 2 2---------->7 8 3 3 8 7
9 4 1 8 7 9 7 8 3 2 2------------>9 4 1 8 8 0 8 8 1 4 9
192---------->202 (you will get output as 2 if you are just dividing by 58 of (string[i]+10) which is wrong....in this case put string[i]='0' if string[i]==':'
hope it will help.
2015-05-03 04:20:13
<snip>

Last edit: 2022-07-26 22:29:30
2015-05-02 21:05:47
i got 21s base on 100,000, how can i do for 1,000,000?
2015-04-28 18:04:21 Anakar Parida
I am able to pass wrong answer but now getting time limit exceeded :(
2015-04-25 11:29:33
Dont know about 5 and 8 as Anakar sugested below that 1 digit number r not palindrime.for 9 20 98 998 6436 are 11 22 99 999 6446
2015-04-24 20:37:02 Gaurav Agarwal
I cant figure out the test cases...
can someone give me the outputs for the following input?
7 //no of test cases
5
8
9
20
98
998
6436
2015-04-23 18:57:41
Single digit number is not a palindrom. It means if i enter 6 it must give 11 as output.is that right?? Or it should be 7

Last edit: 2015-04-23 19:08:07
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.