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-02-21 15:53:21 rish
can we post our code here?i just want to know what am i doing wrong? my code seems to work fine ,but still getting WA .
2015-02-07 11:41:13 Yash
Same code AC in C, but NZEC in Java ...Something's fishy :/
2015-02-07 04:41:33 Yi-Shan Chen
Note for WA:
The last output line can't include the newline, or it'll cause WA...

[reply by cyclops: No, you are wrong.]

Last edit: 2015-02-07 05:03:35
2015-02-02 06:42:26 JATIN ARORA
I am always getting the error (SIGXFSZ).Please help me to remove this error.
My code is running fine on codeblocks.
http://ideone.com/*******

(Francky)⇒ Please read the notes below ; use forum for help, and don't post any codes (nor link).

Last edit: 2015-02-02 14:35:53
2015-01-31 18:06:09 Alexander K
>>>given positive integer K of not more than 1000000 digits<<<

Err..Does that line mean 7 real digits or do we really mean a million figures from 0 to 9 in this number??

Reply (numerix): As it says: 1 million DIGITS!

Last edit: 2015-01-31 20:32:37
2015-01-31 09:28:20 piyukr
Note: There will be NO newline char at the end of last test case.

few test cases:
5 -> 6
9 -> 11
119 -> 121
192 -> 202
5403123 -> 5404045
12 -> 22
200 -> 202
0 -> 1
123456789 -> 123464321
987654321 -> 987656789
322222222 -> 322222223
2015-01-30 17:36:14 Anshul
what is the solution to single digit inputs
2015-01-30 15:06:56 vasu
Can this program have an input of the type 00002?
And in case it does, then according to the description, the solution would be 3. Is that correct?
2015-01-23 08:42:06 Sreeraj
2015-01-14 14:05:49 Anirudha Bose
Keep the following test cases in mind:
9999 -> 10001
99999 -> 100001
5 - > 11
10 -> 11
1299976 -> 1300031

why is the next palindrome for 5 11 ?
should'nt it be 6 ?
it satisfies the definition of palindrome given in the question
2015-01-16 19:55:27 Adalberto Florentino Cleto
my program is perfect with string and all the cases done but de judge tell me WA, some body put more examples
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.