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
ankkt16: 2019-03-13 15:56:34

just form the string dealing with all the cases:)

raycu: 2019-03-13 04:01:00

Lol, I didn't read the prompt and now my code isn't suitable for this. It does accurately determine palindromes, but only if they're smaller than the specified size (I used integer inputs instead of string inputs like a dumbass).

wrong_amoeba: 2019-03-07 19:41:56

I have tested many testcases but still answer is wrong .Can anyone help me?

ayder: 2019-02-27 00:18:35

don't forget cases:
9999 to 10001
1239400 to 1240421 (middle 9 becomes 10)
123999500 to 124000421 (the same)
treating the numbers like strings I just checked if right half is 'upgradable' to left side. If it greater in value just increased middle digit by one and copied left part to right else copied left part to right. If any 9 digits in center increased next

Last edit: 2019-02-27 00:27:12
sibindon: 2019-02-16 19:28:03

I gave up after 2 days....
Actually I was leaving 2 cases....
make sure what you get in these inputs...
56442---->56465 not 56565
56471---->56565

Last edit: 2019-02-16 19:28:23
lunaticgaming: 2019-02-15 04:44:10

Execution Time: .04
My solution worked for all cases that I tested, but it failed in their test.
My solution finally passed on this site when I removed the leading zeros of the input.

deep123r: 2019-02-14 17:14:15

Check for these things
1. Check for Corner Cases(i.e. -all digits are 9 only) ,eg for 99,999,9999,99999(for these just add 2 to the numbers)
2. Leading Zeroes are no problem,e.g. for 000001=001100 is acceptable and 2 is also acceptable.

mighty_joe781: 2019-02-12 07:42:13

I am also getting TLE any ideas.

randm_codr_rs: 2019-02-05 14:15:20

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

venom_black: 2019-01-18 14:37:29

too hard


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%
467 16