PALIN - The Next Palindrome

no tags 

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 Kosowski
Date:2004-05-01
Time limit:2s-9s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6 SCM chicken

hide comments
deep_07: 2015-05-22 14:49:42

All sorts of test cases checked but still getting a WA, can anybody pls check?
Code : http://ideone.com/qcmfSn
Concept : http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/

Had to post it here. Tried registering in the forum 2 times with different email but they never sent a confirmation.

Ptotheextreme: 2015-05-22 12:53:23

i have fallen into the "i have every test correct but still WA" club...

sohail01: 2015-05-19 11:25:17

How many test cases max? Is it mentioned anywhere?

Last edit: 2015-05-19 11:46:04
munex: 2015-05-18 17:51:56

How can I "like" this problem ?

Rakend Chauhan: 2015-05-17 15:26:22

finally got it right!

shivam chandra: 2015-05-15 14:19:24

9 4 1 8 7 9 7 8 3 2 2------------>9 4 1 8 8 0 8 8 1 4 9
not able to rectify this case i m getting output till 941879783
can anyone help me in this ?

rahulsingh80: 2015-05-14 08:07:16

Finally! Got it right!! I feel like I should get a trophy for this. :)
Then again, I need to improve upon checking for various scenarios. It took me many attempts.
A humbling experience.

Last edit: 2015-05-14 21:31:44
arekz: 2015-05-12 08:41:39

Hi, on all colected in comments cases I get correct answer but still I get WA in jugde system. (see: http://ideone.com/ufyoiZ )
@Anakar Parida: I think you should consider the resigne from the use of BigDecimal.

Anakar Parida: 2015-05-08 21:39:22

For the below input it took 0.002547891 sec
Input :-
6
623616231737147634792734623479273472347762394792734
6947274274702734727597205772268628648269472047927498729
927497927496294702749729569729561724162731069164793645926
92749724370274072094728765872057072407120470197401720
72984727498274720749872487289479827498729847
727498298472740720470274070274274072042374

Output :-
623616231737147634792734626437297436741737132616326
6947274274702734727597205772775027957274372074724727496
927497927496294702749729569737965927947207492694729794729
92749724370274072094728765956782749027047207342794729
72984727498274720749877894702747289472748927
727498298472740720471174027047274892894727

Anakar Parida: 2015-05-08 21:27:09

Can anyone really give me input for which my time limit will get exceeded. my java program in ideone is https://ideone.com/BmRqah


Problem's scores 1 vote

Concept difficulty
Concept difficulty 41%
Implementation difficulty
Implementation difficulty 45%
36