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
laidactienbn: 2018-11-06 15:16:20

@omar_elbzt_96 when your program use too much "if" then your time to run the program will be exceeded. It is similar to when you do your exam and you run out of time.

omar_elbzt_96: 2018-11-04 13:33:13

Someone knows what the problem is when we have " TIME LIMITE EXCEEDED" while in the program there is no mistake.

ianc1339: 2018-10-28 09:00:54

It is possible to use cin/cout and get AC

Rohit Agarwal: 2018-10-22 17:24:45

The input can have leading zeros. Be careful of input like this 000001. Simply consider it as 1. Costed me 3 WA

stevezl1x: 2018-10-21 07:28:15

Last edit: 2018-10-21 07:51:06
ashrockzy: 2018-10-19 07:26:16

getting wrong answer though working fine on my local pc . Any testcase I'm missing ?

ashrockzy: 2018-10-19 07:19:21

any alternatives to cin and cout in c++ ?

dragost_305: 2018-10-11 19:34:18

getting non zero exit error in java though all cases are working properly in netbeans

ben_d: 2018-10-09 16:56:26

Getting time exceeded even with fail-fast implementation in java...

mr_volatile: 2018-10-09 16:00:12

In my problem, default test case and test case '9' is solved upto 14 times '9', But still getting wrong answer.


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 49%
322 9