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
mariceles: 2016-07-22 13:55:50

I really should grow the habit of reading the question before answering. I solved the question using integer types thinking the number would be less than 1000000, but it was the number of digits :(

jigarjani: 2016-07-22 07:41:55

All test cases running on eclipse and ideone (java).. In spoj, NZEC runtime error. HELP PLSSS !!!! Its super frustrating..

mxfce: 2016-07-19 12:24:11

Don't use Big Integer its too slow , I suggest you use int array to store digits. when K =191 makes sure its output is 202 not 101. GOOD LUCK!

shivam_04: 2016-07-18 04:48:10

My code is working correctly in my IDE but run time error here...!! pls help and all my test cases are working....!!

Last edit: 2016-07-18 04:50:53
kpiyush26: 2016-07-16 20:56:27

Last edit: 2016-07-16 20:58:34
levim: 2016-07-15 17:47:10

Thanks to @Dushyant Singh , 2 times WA using scanf. AC after switching to cin

milos94: 2016-07-07 17:38:23

I'd just like to say to all of you who are getting WA and have tried all of those cases that people posted, got them right, and got right answer in ideone, or wherever you tested your code. When you print answers print them in one line separated by a space. So no endl,\n or anything like that only ' '. Trust me I got 10+ wrong answers because of this.
Also use string because numbers can have 1000000 digits.
Palindrome from 00000 is 00100. And single digit numbers are palindromes so just increment them. Don't forget to test those edge cases that everyone is posting.

Last edit: 2016-07-07 17:44:20
shivani_10: 2016-07-06 17:42:17

Please make it clear that the value of 'k' should be less than 1000000 or the value of 'k' should contain less than 1000000 'digits'? As in the question it is mentioned as 'not more than 1000000 digits'.
And also what is the maximum limit of test cases that can be taken?

mickey_v: 2016-07-06 07:51:46

what about leading zero ? do we need to take care of them?

san93st: 2016-07-02 16:25:08

TLA :(


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 PERL 6

Problem's scores 1 vote

Concept difficulty
Concept difficulty 39%
Implementation difficulty
Implementation difficulty 48%
138 5