PALIN – The Next Palindrome

Link SPOJ: https://www.spoj.com/problems/PALIN/

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.

Ouput

For each K, output the smallest palindrome larger than K.

Restriction

Time limit:2s-9s
Source limit:50000B
Memory limit:1536MB

Example

Input:
2
808
2133

Output:
818
2222

Please try to solve first, before moving into the solution.

Solution:

http://fainbory.com/8ium

AC Code:

http://fainbory.com/8ixp

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s