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
Vijay: 2015-04-14 10:55:38

Not as easy and mathematical as it looks .
As written by others in comments "its all about nine"

PRAFUL ANAND: 2015-04-11 15:37:36

after submission of code if status shows wrong answer. please please...... show me for which test case my code is showing wrong answer and what is the expected output and your output for that particular test case. It will be helpful to debugg the program.

Last edit: 2015-04-11 15:41:58
Punit Bhatt: 2015-04-11 00:23:28

My submission is not getting accepted but "runtime error (SIGSEGV)" is being displayed. Can someone please explain what this means ?? When i tested the program, the outputs were right. But still this error is being displayed.

Asad Rahman: 2015-04-04 18:22:02

Great problem...basically its all about nine :)

Kyezil: 2015-04-04 14:47:33

You have to print the NEXT palindrome whether the current number is or not.

CHRIS: 2015-04-04 12:50:55

why 808 isint a pallindrom

Subham: 2015-04-04 07:57:55

It is giving right output, but don't why is telling wrong answer.
<script src="http://ideone.com/e.js/UbxmKu" type="text/javascript" ></script>

hanliyao: 2015-04-03 03:45:16

i guess:
the positive integer k of not more than 1000000 digits is something about the length of the K

im9: 2015-03-31 14:59:22

Is it necessary to use vectors?

sughosh v kaushik: 2015-03-30 17:53:16

Should I use BigInteger for this problem or int is enough?Its giving me NZEC


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