B. Palindromic Numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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!

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.

Example
Input
3
2
99
4
1023
3
385
Output
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$$$.