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
sukriti_verma: 2015-12-23 19:09:22

Go through ALL the comments to debug if you're getting a WA for no apparent reason. No shit. You'll find the reason.

lgarvey: 2015-12-21 00:01:39

Getting NZEC despite my implementation working perfectly on my computer, even with a single 1 mill input, on python 2.7.1. Argh!

kunal3110: 2015-12-15 18:31:58

getting NZEC

Vardi Narendra: 2015-12-14 09:31:20

Try this input
1
94187978322

pparas007: 2015-12-13 15:25:38

Code is running perfectly on local machine with small trial input combinations!
but getting 'NZEC runtime error' in Java language! what could be the problem???

himanshu_1997: 2015-12-05 13:51:07

All my outputs are correct but on submitting the code it's showing wrong answer
and what does : " Numbers are always displayed without leading zeros. " mean?

vigneshkv: 2015-11-22 19:08:21

<Beginner feedback>
<c++ 5>
I took almost 1week for this problem.if you get TLE or Signal 11 error,there is a mistake in your implementation.try optimizing the code ,reduce the number of loops.
if you get signal 11 error ,there is a problem in some initialisation.
i used two dimensional array which caused TLE.i can say single dimensional array is better.
reducce the loops for not letting it getting stuck in TLE.

Last edit: 2015-11-22 19:09:45
miki_24: 2015-11-18 15:58:05

why "time limit exceeded"? my code works perfectly on my computer and in Ideone.com
This inputs 11
34896787423968728967892736
236723867238967289367283967289, 238967238672837628937628937629731346716241386972409682365107365, 2587238597238461876343285468034689347616347826369850960347628364234293840, 745847583745, 3458349573485729865 etc are solved in 0,03 sec , I'm writing in python 3.5, when submitting choosing Python 3.4 . Can't get what's wrong
please help

Last edit: 2015-11-18 16:02:38
Dushyant Singh: 2015-11-15 17:27:21

For those who are getting WA even after confirming all test cases use cin instead of fflush and scanf. I just changed that in my code even without looking at it(which was months old) and got AC. scanf is a mess for strings and char arrays.

Last edit: 2015-11-15 17:29:57
rc_alex36: 2015-11-15 16:25:27

Confirmed that there are nothing wrong with the test cases. If u get a WA then there's some problem with ur code. I literally used an hour to debug just to reach an Accepted. Try 999, 8997, 3, 9, 100, 1000, 9999 beforehand.


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%
467 16