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.

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$.

Samples

3
2
99
4
1023
3
385

32
8646
604