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
uchihasurvivor: 2019-04-28 15:22:12

AC - 0.04s
1.Don't try generating palindromes.
2.Take input as string and edit it to form a palindrome.
3.Replicate right part same as left part. compare with input if still it isn't greater then add 1 to right most number in you left part and replicate the same on right part. (Don't forget to handle odd length case)
Test cases :
123456 -> 124421
1234567 -> 1235321
9999 -> 10001
99999 -> 100001
1 -> 2
9 -> 11

klmo: 2019-04-18 18:49:26

AC in one go :) but 2.76 time in JAVA, can it be faster in java?

klmo: 2019-04-18 18:46:40

few interesting test case:
2991
3994
9999
5448
65343454
etc

solskgaer: 2019-04-09 12:54:09

I tested 4 scenarios: all 9s, the number itself is a palindrome, numbers like 54321 that just need to mirror the left side to right side and numbers like 12345 that need to mirror the left side to right side and deal with carries, my code passed all 4 cases and work with 1 digit numbers and numbers with leading zeros, but I still failed, any help?

Last edit: 2019-04-10 04:46:08
nguyenthehop: 2019-04-03 11:10:18

I need your help. I don't known where i wrong

shogun420: 2019-04-02 11:25:50

I guess all my test cases are correct..but it shows time limit exceeded..what should I try next??

Last edit: 2019-04-02 11:27:16
subhashs: 2019-03-28 18:19:31

0.06s

phoenix2021: 2019-03-23 12:33:32

anyone who has solved the probem in python3.5?
I am getting TLE despite getting correct answer in my local machine for all test cases

Last edit: 2019-03-23 12:33:48
thecyberalien: 2019-03-22 20:01:26

I am getting runtime error (sigsegv). but it is working perfectly in my compiler.

danfrown: 2019-03-17 07:38:17

I don't get it. After taking all sorts of input, they are saying wrong answer. However, it works perfectly on my editor offline. I have taken into account
big input,
leading zeroes
corner cases
I am using C. Any ideas what to do?


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