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
ashwini_571: 2019-01-15 21:26:34

Last edit: 2019-01-15 21:26:56
squirrelli: 2019-01-03 14:02:41

If input is 010,000, isn't the output 10,001?

sehgal_divij: 2019-01-02 13:21:19

runs on my machine but fails here.
note that I am using -std=c++11 flag while compiling on my device. It works on my device but fails with the following error here:

runtime error(SIGABRT)

Works on ideone

Suggestions on what to do?

Link to working version on ideone:
https://ideone.com/bmmZHx

Last edit: 2019-01-02 13:41:01
nitin_uniyal: 2018-12-23 05:14:36

running time 0.56 s.
Don't convert the string to int or long int anywhere. Strip the input to remove '\n'. Use the list of string characters because strings are immutable in nature. Characters
Consider all cases e.g.
'0', '9',' 99', '1991' etc.

spyhawk_74: 2018-12-22 12:59:57

Finally ACed in 9th attempt.
For future solvers:: Make sure you do not give up. It will take time, For me it was roughly 8 hours. A good ad hoc problem. Make sure that you implement your logic properly.

Maneesh Sharma: 2018-12-18 10:11:49

If k is 999, should the output be 1001 ?

Last edit: 2018-12-18 10:12:34
fuyanghua: 2018-12-14 09:53:21

I have run over 10^20 times on my computer and it only cost 2s.However,I got TIME LIMITE EXCEEDED when submit every time. Who can tell me why?

Last edit: 2018-12-14 10:13:03
dhananjay_gore: 2018-12-12 07:25:17

I'm getting runtime error NZEC in this problem while submitting
but perfectly running on ideone platform

Last edit: 2018-12-12 07:26:02
aashish_a2z: 2018-12-10 22:54:24

This is a nice problem.....Try to consider all the cases........Not a easy problem so don't worry it will take some time to solve...try to optimize your code....
For WA try to consider boundary cases and u may consider some of the test cases given in comment section.

sudesh12345: 2018-12-08 09:39:37

Anyone please help me.
I tried many times by taking the number as int .i am also done with the test case starting with 0 i.e i am taking 010 as 10.Though it is showing wrong answer every time. i am getting correct answer in my compiler.

Last edit: 2018-12-08 09:41:33

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