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
Rajat: 2015-01-12 19:48:47

extremely good question. :)

hanu_man: 2015-01-08 15:28:22

it is all about nines....

praveen anuranjan: 2015-01-08 10:13:59

<snip> every answer is coming true and still giving WA someone plzzz help

Last edit: 2022-07-26 22:29:18
Trailblazer: 2015-01-07 14:58:52

Does inputs are not separated by '\n' ?
If not then how it would be read.

Novice Whistler: 2015-01-07 04:48:19

@Punit, you have taken the data type of inputs as long. This will not be able to hold a 10000 digit number. So, the test cases beyond the "capacity" of long will not pass.Try using string for this.

Last edit: 2015-01-07 04:49:22
Ankit Srivastava: 2015-01-03 08:11:38

Please help point where I am hitting TLE - <snip>

Last edit: 2022-07-26 22:29:13
Punit Bhatt: 2015-01-02 11:33:13

Tried solving this problem. Got right answers in all cases but am getting wrong answer here in spoj. Please help me out
ideone.com/iu5T4S

Nazmul Hossain: 2014-12-29 06:38:12

I am getting runtime error NZEC ....

Ankit: 2014-12-27 05:17:21

Its a general question. I am not sure of the answer.
How should the input ouput sequence be for problems.?

Input
Input
Input
Input

Output
Output
Output
Output

" OR "
Input
Output
Input
Output
Input
Output

Last edit: 2014-12-27 05:17:46
Petar Jesic: 2014-12-26 20:40:53

@Dan: thanks a million, had that problem.


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