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
the_imp: 2015-01-14 20:43:19

http://ideone.com/7ejK6Y
getting sigbart...plz help

Ani: 2015-01-14 14:05:49

Keep the following test cases in mind:
9999 -> 10001
99999 -> 100001
5 - > 11
10 -> 11
1299976 -> 1300031

Last edit: 2015-01-14 14:07:06
Kaushik Nath: 2015-01-13 17:38:40

i am taking input through strings
and getting correct answer at ideone but not at spoj
please help

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

http://ideone.com/mA5RqI every answer is coming true and still giving WA someone plzzz help

Last edit: 2015-01-09 10:58:53
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 - http://ideone.com/sy5S0c

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


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