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
2014-06-26 20:40:48 Mitch Schwartz
@Asheesh: Complaining angrily about not knowing how things work on the first day of joining a site isn't what I would call interesting. (1) Python is a slower language. There are several Python3 solvers for this problem, but you may need to pay more attention to optimisation concerns compared with other languages; (2) NZEC in Java should mean an exception was thrown -- an error that could be prevented by careful programming; (3) compilation errors are the easiest for users to diagnose; you can click on "compilation error" and read the error yourself. You can also see the name of the compiler when you submit. It should be no surprise that some compilers behave differently from others.
2014-06-26 20:20:35 Asheesh Pathak
This is bullshit. Got time limit exceeded in Python 3, run time error in JAVA 6 and f**king compilation error in C++ 4.3.2 even though they all work fine in my system, and the interesting thing is that I joined SPOJ only today.
2014-06-21 12:18:31 Sethu Iyer
Very good problem , spent 7 hrs in this problem for AC in 1 go and i got it. simply worth it
2014-06-18 22:58:07 Jens Stimpfle
Warning: DOS Line endings (\r\n)
2014-06-08 05:38:53 chin
after long trial ...finally AC!!!!..:D
2014-06-02 10:23:56 Mitch Schwartz
@Ɓukasz Kuszner: Thank you!
2014-06-02 08:42:37 kuszi
@Mitch Schwartz && cegprakash: after the long rejudge it appeared that about 30% of previously accepted solutions was incorrect. Thank you very much!

Last edit: 2014-06-02 08:43:36
2014-05-13 15:09:33 Dmitri
Was worried if my program would take 1 000 000 chars string with Console.ReadLine() in C#. But got solution accepted at the first attempt :)
2014-04-24 20:24:06 The Mama of Coding
awesome problem!!! but not for beginners... took me 6 hours to fully understand it. thumbs up
2014-02-12 06:51:43 ANKIT KUMAR CODOPEDIAC
can u plz tell me at which test case this is giving wrong ans?

[code removed]

"1. Don't post any source code here."

Last edit: 2014-02-12 08:04:04
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.