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
eng_hardik: 2018-09-02 07:44:57

A great problem with a variety of test cases , so before careful about all the possibilities.

gvsharma: 2018-08-28 07:10:21

getting time exceeded..

rajatsahay: 2018-08-25 09:27:05

it says time limit exceeded..ran it on ideone.com and total time taken was 0.04s

naruto17: 2018-08-19 22:02:21

for run time errors ;
try this
1
9999999999
ans : 10000000001
u will get the answer surely.

nobody550: 2018-08-04 21:17:51

Check for '9'
Input
9
Output
11

aquib_ansari: 2018-07-15 17:44:49

Do we need to consider -ve numbers as well?

shivansh306: 2018-07-15 12:39:04

Run time error in python3 I am defining a function for solving the problem

rogu_auto: 2018-07-13 16:25:02

pay attention to "K of not more than 1000000 digits"! u can't use a numeric variable to save K, u need a string variable!

phuongnguyen96: 2018-07-11 11:19:55

runtime error. i don't understand, with java!!

mrzydeco: 2018-07-08 06:38:12

The hapless solver of this solver of this problem might have quite reasonably assumed that the input would consist only of digits and newline characters. If you're going to allow stray whitespace at the beginning or end of input lines, that should be mentioned in the input specification.

It really is silly that we have to GUESS this sort of detail IN THE DARK. This flaw seriously vitiates the quality of an otherwise really good problem.

Last edit: 2018-07-09 00:00:50

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