L. Sasha and the Homework
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Having lost all the money for a gift, Sasha decided to give a different gift, specifically — to help his girlfriend with her homework:

Let's define the function $$$f(x) = (x \wedge (x + 1)) \oplus (x \wedge (x - 1))$$$.

Where $$$\wedge$$$ denotes the bitwise AND operation and $$$\oplus$$$ denotes the bitwise XOR opearation.

Let's define the function $$$g(x)$$$ as the number of $$$y$$$ ($$$1 \leq y \leq 2^n - 1$$$) for which $$$f(y) = x$$$ holds true.

Also given is the number $$$a$$$ ($$$0 \leq a \leq 2^n - 1$$$). It is required to find the maximum value of $$$a \oplus g(x)$$$.

Help Sasha please his girlfriend and solve her homework for her.

Input

This problem consists of several test cases.

The first line contains a single number $$$T$$$ ($$$1 \leq T \leq 5000$$$) — the number of test cases.

Then follows their description.

The first line contains a single number $$$n$$$ ($$$3 \leq n \leq 10^5$$$).

The second line contains a string $$$a$$$ consisting only of characters "0" or "1" of length $$$n$$$ defining the number $$$a$$$ in binary notation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$

In other words, the number defined by the string will be equal to $$$2^{n - 1} \cdot a_1 + 2^{n - 2} \cdot a_2 + \ldots + 2^{0} \cdot a_n$$$

Output

For each test case, output the answer to the problem as a binary string of "0" and "1"

Example
Input
5
3
010
4
1000
4
0010
4
1101
4
1111
Output
011
1110
0110
1111
1111
Note

Consider the first test case:

$$$ f(1) = 0, f(2) = 2, f(3) = 2, f(4) = 4, f(5) = 0, f(6) = 2, f(7) = 6 $$$

Therefore:

$$$ g(0) = 2, g(2) = 3, g(6) = 1, g(4) = 1 $$$

Hence, the maximum value is achieved at $$$x = 2$$$ or $$$x = 6$$$. ($$$2 \oplus 1 = 3$$$)