1700B.md (1813B)
1 Source: https://codeforces.com/problemset/problem/1700/B 2 3 B. Palindromic Numbers 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 During a daily walk Alina noticed a long number written on the ground. Now Alina wants to find some positive number of same length without leading zeroes, such that the sum of these two numbers is a palindrome. 22 23 Recall that a number is called a palindrome, if it reads the same right to left and left to right. For example, numbers $121, 66, 98989$ are palindromes, and $103, 239, 1241$ are not palindromes. 24 25 Alina understands that a valid number always exist. Help her find one! 26 27 Input 28 29 The first line of input data contains an integer $t$ ($1 \leq t \leq 100$) — the number of test cases. Next, descriptions of $t$ test cases follow. 30 31 The first line of each test case contains a single integer $n$ ($2 \leq n \leq 100\,000$) — the length of the number that is written on the ground. 32 33 The second line of contains the positive $n$-digit integer without leading zeroes — the number itself. 34 35 It is guaranteed that the sum of the values $n$ over all test cases does not exceed $100\,000$. 36 37 Output 38 39 For each of $t$ test cases print an answer — a positive $n$-digit integer without leading zeros, such that the sum of the input integer and this number is a palindrome. 40 41 We can show that at least one number satisfying the constraints exists. If there are multiple solutions, you can output any of them. 42 43 Example 44 45 Input 46 47 ``` 48 3 49 2 50 99 51 4 52 1023 53 3 54 385 55 ``` 56 57 Output 58 59 ``` 60 32 61 8646 62 604 63 ``` 64 65 Note 66 67 In the first test case $99 + 32 = 131$ is a palindrome. Note that another answer is $12$, because $99 + 12 = 111$ is also a palindrome. 68 69 In the second test case $1023 + 8646 = 9669$. 70 71 In the third test case $385 + 604 = 989$.