PALIN - The Next Palindrome

no tags 

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


Added by:Adrian Kosowski
Date:2004-05-01
Time limit:2s-9s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6 SCM chicken

hide comments
shomit: 2015-04-25 11:29:33

Dont know about 5 and 8 as Anakar sugested below that 1 digit number r not palindrime.for 9 20 98 998 6436 are 11 22 99 999 6446

Gaurav Agarwal: 2015-04-24 20:37:02

I cant figure out the test cases...
can someone give me the outputs for the following input?
7 //no of test cases
5
8
9
20
98
998
6436

shomit: 2015-04-23 18:57:41

Single digit number is not a palindrom. It means if i enter 6 it must give 11 as output.is that right?? Or it should be 7

Last edit: 2015-04-23 19:08:07
Szymon: 2015-04-20 22:42:28

nice problem for tests coding
1 do brute force program
2 do your algorithm
3 compare results

ashish: 2015-04-20 20:49:43

Hello admin/problem setter, can you please check why I am a getting wrong answer? Id: 14128402

Also can you please give at-least 1 testcase where I am getting a wrong answer?

Anakar Parida: 2015-04-19 16:32:41

I am also fed up with wrong solution. Handled all cases from 1 to 999999999999999999. Dont know what else is needed

Eknoor Jassal: 2015-04-19 15:49:39

I would restate what everyone is saying. I not " all about nines". Its about "all nines" ;)

Anakar Parida: 2015-04-18 19:46:17

One small suggestion for all people who are facing "wrong answer".. Single digit number is not palindrome. Do make sure your code handles it.

shomit: 2015-04-17 21:57:10

i have tried this code for every case yet it says wrong answer.Please list the difference test cases.....ughh i am fed up with this one

saki: 2015-04-16 18:36:46

Guys i am new to SPOJ, not sure where to post my source code so that someone can check why it is showing wrong answer, I got exact o/p as mentioned in the question when done in Putty. Please help!


Problem's scores 1 vote

Concept difficulty
Concept difficulty 43%
Implementation difficulty
Implementation difficulty 46%
26