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
Zishan Ahmad: 2015-03-05 13:30:14

Admin, I was getting TLE and then i read your comment that input does not end on new line. is that the case with individual input numbers as well ? i modified the program to include both new line as well as space to separate input numbers but still getting TLE

palak bhatia: 2015-03-04 16:30:05

please indicate whats "wrong" with my answer submitted..since my all test cases are coming out to be correct...my not able to identify the problem

Last edit: 2015-03-04 16:30:42
John Jost: 2015-03-02 07:02:48

Just wanted to comment that the input does not end on a newline character. Check that your program is not expecting one if it gets TLE.

John Jost: 2015-03-02 06:59:38

Narendra: For a single digit the output would be the next largest single digit. So 7 would be 8. 9 would be 11.

Narendra pal: 2015-03-01 22:01:29

Admin....what should be output of single digit int.......and if u can hint some corner cases.....thanks in advance

Last edit: 2015-03-01 22:13:07
fullmetal: 2015-02-28 17:06:17

Thanx for u r great help Piyush

Foo: 2015-02-28 11:30:09

I have considered all possible test cases and the output seems to be correct. Still it is saying "wrong output".. Please Help Me..!!

sasirekha: 2015-02-26 11:12:19

gopala krishna i answering to ur doubt.
palindrome means the letter we read from right to left and left to right must remain same.eg:mom,818.you misunderstood value 2, it indicates number of input value.

gopala krishna: 2015-02-24 15:05:00

small doubt in the question...i couldnt understand the line numbers should be displayed without leading zeroes..i am new.please explain me that line

re(vamsi): you have to output the smallest palindrome larger than K, so if the input is 2 you have to output 3 not 11. Also you shouldn't print any leading 0s you have to print 3 not 03, 003 or something else

Last edit: 2015-02-25 17:07:32
gopala krishna: 2015-02-24 14:59:54

i have a small doubt.
if. we give input 2 why cant the output be 11 because it is also a
palindrome ...please clarify my doubt


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