CF1700B Palindromic Numbers

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. 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. Alina understands that a valid number always exist. Help her find one!

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. 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. The second line of contains the positive $ n $ -digit integer without leading zeroes — the number itself. It is guaranteed that the sum of the values $ n $ over all test cases does not exceed $ 100\,000 $ .

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. We can show that at least one number satisfying the constraints exists. If there are multiple solutions, you can output any of them.

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. In the second test case $ 1023 + 8646 = 9669 $ . In the third test case $ 385 + 604 = 989 $ .