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
raunak_sharma: 2016-08-31 18:23:37

I got the right output but when i submit the solution, it says wrong answer. Can there be a problem with " given positive integer K of not more than 1000000 digits," ? I've used long long int for that. Please help.

coddict: 2016-08-31 09:42:01

what is constraints of test cases.
0<t<?

manish_hacked: 2016-08-30 14:13:11

Finally AC after too much hard work!!!
Run your code for small number like one digits numbers especially 9

ganeshjadhav: 2016-08-29 18:42:47

solved it in 0.06sec

suchigupta: 2016-08-28 21:22:08

gave correct answer of all test cases(given in comment also) on ideone but on submission SIGSEGV :((

sxdcffg: 2016-08-26 09:59:53

For Python users, if your non-brute force solution is timing out try avoiding converting into lists or an integer. For a 1000000 digit number, these functions become very expensive in terms of time.

imad315: 2016-08-21 20:20:55

what the role of t integer(number of test) ? how can i include it in my code?

leepx: 2016-08-20 05:46:59

You can try this number.
in:39474657
out:39477493

drajingo: 2016-08-19 13:53:03

After 2 SIGSEGVs and 12 WAs, getting that AC was pretty much the best feeling in the world. :D :D
Keep working on it, and test your code with small inputs where the answer can be verified by brute force.

Ashutosh Singh Chandel: 2016-08-05 01:11:51

go to @ vector1996 's comment . helped me..


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 49%
150 5