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
2016-12-27 12:19:37
spent a complete day in june when it was my day 1 with competitive programming . 5-6 Wrong answers and left .
Spent 1 hour today . proved the correctness of algo before writing the code . AC in one go . (except 1 WA due to a typo) .This questions is truly worth the time !!
2016-12-23 15:04:50
my code is giving correct ans on code chef then can any1 tell whats wrong here

[ code snipped ]

Last edit: 2016-12-23 15:34:47
2016-12-23 14:35:58 Bharath Thiruveedula
My program solves all possible cases, but overlooked the case 11, 1111, 111111
2016-12-22 11:51:45
Why I'm getting wrong answer even if my program is working correctly, even for input 9 ?
Can SPOJ provide me the test case for which I'm getting wrong answer?

Last edit: 2016-12-22 11:53:23
2016-12-16 10:15:09
getting TLE
2016-12-15 16:44:16
Can anyone please help me to remove this exception
Exception in thread "main" java.util.NoSuchElementException
at java.util.Scanner.throwFor(Scanner.java:862)
at java.util.Scanner.next(Scanner.java:1485)
at java.util.Scanner.nextInt(Scanner.java:2117)
at java.util.Scanner.nextInt(Scanner.java:2076)
at Main.main(Main.java:77)
2016-12-07 08:15:38
Thanks @dusan_1989 for test case. Test case with number 9 is super effective :)
2016-12-06 20:42:15
why i always get wrong answer error on this site.
doing coding from 10 years and finish almost all websites questions.....
2016-12-04 03:32:27
Thanks @vector1996 for test cases:)
2016-12-01 13:19:19
Great problem. Learned a lot. Must try for beginners :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.