In the $2022$ year, Mike found two binary integers $a$ and $b$ of length $n$ (both of them are written only by digits $0$ and $1$) that can have leading zeroes. In order not to forget them, he wanted to construct integer $d$ in the following way:

• he creates an integer $c$ as a result of bitwise summing of $a$ and $b$ without transferring carry, so $c$ may have one or more $2$-s. For example, the result of bitwise summing of $0110$ and $1101$ is $1211$ or the sum of $011000$ and $011000$ is $022000$;
• after that Mike replaces equal consecutive digits in $c$ by one digit, thus getting $d$. In the cases above after this operation, $1211$ becomes $121$ and $022000$ becomes $020$ (so, $d$ won't have equal consecutive digits).

Unfortunately, Mike lost integer $a$ before he could calculate $d$ himself. Now, to cheer him up, you want to find any binary integer $a$ of length $n$ such that $d$ will be maximum possible as integer.

Maximum possible as integer means that $102 > 21$, $012 < 101$, $021 = 21$ and so on.

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains the integer $n$ ($1 \leq n \leq 10^5$) — the length of $a$ and $b$.

The second line of each test case contains binary integer $b$ of length $n$. The integer $b$ consists only of digits $0$ and $1$.

It is guaranteed that the total sum of $n$ over all $t$ test cases doesn't exceed $10^5$.

For each test case output one binary integer $a$ of length $n$. Note, that $a$ or $b$ may have leading zeroes but must have the same length $n$.