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


hide comments
loser_404: 2021-06-02 16:17:08

One of the best problems ever faced.

botter_code: 2021-06-02 12:54:39

lessgoo

ninh0855250956: 2021-05-10 08:40:49

2 hrs got AC

slash_1: 2021-04-14 19:55:48

why the next palindrome of 0003 is 0110 and not 4 ?

rushi2001: 2021-03-22 21:59:34

Started On 12 am
AC at 2.29 am

wowthecoder: 2021-03-20 08:39:44

AC with Java after 5-6 TLEs...
Use BufferedReader and BufferedWriter for fast I/O, use strings and char instead of int array. DON'T convert the input number to BigInteger as it will slow your program down.
Learnt quite a bit... Good luck!

adrian_mole: 2021-02-22 01:56:55

The challenge clearly states: "Numbers are always displayed without leading zeros." So, how does 0003 give 0110 (one leading zero) not 4? And how does 0012100 give 0013100 (two leading zeroes) rather than 12121?

makhan_28: 2021-02-20 10:26:58

Good Problem!!
My advise to approach this problem is take some sample different cases, analyse them and try to come up with its implementation.
Thanks for different test cases It helped a lot!! :)

rahultwr_ankur: 2021-02-19 14:47:33

After 2 hour struggling ..finally got AC..
thanks to shreyas_07 for TCs..it helped a lot

Last edit: 2021-02-19 14:47:55
wille_25: 2021-01-08 20:58:32

Finally AC --- (0.02s)
The Input given by shreyas_07 is not working correctly (infinite loop occurs in c++),
But it Still Got AC ;


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

Problem's scores 1 vote

Concept difficulty
Concept difficulty 37%
Implementation difficulty
Implementation difficulty 50%
453 15