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
malavan: 2016-09-24 15:45:02

@narutohokage_1 ip 00000 op 00100... is not violating the principle of palindrome ???
then why ???

narutohokage_1: 2016-09-24 13:06:20

For All People Who Are Getting WRONG ANSWER MANY Times....

1. If the input is a single letter then the output can be 11 or that number + 1.
Example : Input : 1
Output : 2 or can be 11 . (Both Are Correct). ( i have myself checked it)

2. Do not listen to comments who are showing to do with this or that method. Apply your own brain.

3. For input like 00000 answer is 00100 (it is absurd maybe this case will not be even in input file) , I do not know whether a number like this will be in the input file or not , but if your code is like mine answer would automatically come to be 00100 for 00000 and things like that. DO NOT WORRY ABOUT THAT. I do not think what would be in test case because they do not make sense.

4. If after the answer to the last case your program is inserting a new line it won't cause any problem( i tried both ways with and without the new line after the last output) . It worked both times. You can still choose to not print the new line after last output.

5.If you are taking more than a day or week to solve this problem it is absolutely right. Your brain is having a workout and it will help you later. Those who are saying it is an easy problem have done it. so it is easy for them . do not get demotivate that you are not able to solve it. Just be persistent and do not give up.

6. At last check these test cases. : ( thanks @vector1996 for test cases)

Input :
12345
14325
12325
52321
12945
12925
99998
99999
98999
89999
231
132
268545813
208545813
2862
2682
2221
1222
2993


o/p
12421
14341
12421
52325
13031
13031
99999
100001
99099
90009
232
141
268545862
208555802
2882
2772
2222
1331
3003

7. REMEMBER THAT WE HAVE TO PRINT NEXT PALINDROME. SO IF INPUT IS 808 ( WHICH IS ITSELF A PALINDROME) WE HAVE TO PRINT 818 ( THE NEXT PALINDROME)

8. it is up to 1000000 digits long number. Not up to number 1000000.

DO NOT GIVE UP . I WAS ABOUT TO. THEN I SOLVED IT. FIRST FIND THE SOLUTION TO SMALLER NUMBER LIKE 123456 AND 998999 AND 2993 AND 28998 ON COPY WITH PEN AND PAPER. DO NOT WORRY ABOUT A LARGE NUMBER. After finding the method implement it using a large number .

Last edit: 2016-09-24 13:08:46
balaji_04: 2016-09-23 18:52:30

it always show runtime error, segmentation fault(SIGSEGV) . i got the right output in diff compilers.

avishek_arora: 2016-09-22 20:33:12

I'm using python, guy any hints regarding this problem?

Last edit: 2016-09-22 20:35:19
avishek_arora: 2016-09-22 20:33:12

If it's something else then let me know.

Last edit: 2016-09-22 20:34:40
avishek_arora: 2016-09-22 20:33:12

@malavan i Think if you entered a single digit number less than 9, the next palindrome would be that number + 1, according to the palindrome definition.

malavan: 2016-09-22 15:23:33

if the input is single digit ,is that output will be 11 ????

nishabha: 2016-09-13 16:06:34

@imad315: It's the no. of times your code will be run for different sets of input.
In code: main() {
int noOfTestcases; cin >> noOfTestcases;
for(int i=1; i<=noOfTestcases; i++)
{
// write the actual code that solves each testcase
}
} // end of main

shaan001: 2016-09-05 12:52:01

NZEC java....

sifors: 2016-09-03 22:21:19

What wrong with this compiler? My solution dont accept every time but on VS it is running smoothly ((


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 PERL 6

Problem's scores 1 vote

Concept difficulty
Concept difficulty 39%
Implementation difficulty
Implementation difficulty 49%
152 5