Palindromic Numbers
Description
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.
Input
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$.
Output
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.
Samples
3
2
99
4
1023
3
385
32
8646
604
Note
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$.