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
ash_maurya: 2017-09-21 08:55:26

@deepjyoti30 If Online Judges start giving you an AC based on what you believe, almost everyone who had attempted this problem would have solved this problem. Not only this, questions is every Contest on every CP platform. You must be missing some corner cases or you are using 64 bit integer variable to calculate it. Like many have already said, it's not a straightforward brute-force solution. Check for corner cases like 9999999, 2939393 , etc. Try harder.

Last edit: 2017-09-21 08:56:34
deepjyoti30: 2017-09-20 17:42:32

Just submitted the solution. Working all right on my system but they marked it as wrong answer

rama_krishna1: 2017-09-17 13:25:00

How is it a string problem?My code is not working for large inputs.I used C lang and used unsigned long long for the numbers.

sir69: 2017-09-15 15:44:17

You need to treat it like a string instead of an integer. The problem is not defined properly.

theoden91: 2017-09-13 09:56:55

Hope that can be useful. There are no leading zeros, so don't think about implementing that.
Test input that I used:
9
0
1
9
99
12
808
2133
321123
94187978322

Correct output:
1
2
11
22
101
818
2222
322223
94188088149

payal2621: 2017-09-12 19:43:10

remember its just simple just use reverse function
and plz dont forget new line

Simran Saha: 2017-09-08 16:19:04

There is a serious mistake in the output description here. Judge accepts solution with answers printed with space instead of newline.
Finally AC

trigun_123: 2017-09-07 21:08:23

what to do if getting wrong answer.
bt its giving rt ans on linux

kamlesh_2209: 2017-09-01 06:58:25

thanks @milos94 ... your comment about printing answer with just a space and not endl helped me....

jaykay12: 2017-08-30 22:25:48

AC in 3rd Go. :) Nice Problem. Be Careful with Number 9. :p Actually a String problem not an integer.


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 38%
Implementation difficulty
Implementation difficulty 49%
239 7