Puzzle From the Future
Contest: Codeforces Round 696 (Div. 2)
Difficulty rating: 800
Tags: greedy

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.

Input format:
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$$$.

Output format:
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$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$b = 0$$$ and choosing $$$a = 1$$$ gives $$$d = 1$$$ as a result.

In the second test case, $$$b = 011$$$ so:

- if you choose $$$a = 000$$$, $$$c$$$ will be equal to $$$011$$$, so $$$d = 01$$$;
- if you choose $$$a = 111$$$, $$$c$$$ will be equal to $$$122$$$, so $$$d = 12$$$;
- if you choose $$$a = 010$$$, you'll get $$$d = 021$$$.
- If you select $$$a = 110$$$, you'll get $$$d = 121$$$.

In the third test case, $$$b = 110$$$. If you choose $$$a = 100$$$, you'll get $$$d = 210$$$ and it's the maximum possible $$$d$$$.

In the fourth test case, $$$b = 111000$$$. If you choose $$$a = 101101$$$, you'll get $$$d = 212101$$$ and it's maximum possible $$$d$$$.

In the fifth test case, $$$b = 001011$$$. If you choose $$$a = 101110$$$, you'll get $$$d = 102121$$$ and it's maximum possible $$$d$$$.

Example input:
5
1
0
3
011
3
110
6
111000
6
001011

Example output:
1
110
100
101101
101110

Editorial:
Hint $$$1$$$: Should we always make first digit of $$$d$$$ not equal to $$$0$$$? How can we do it?
Hint $$$2$$$: Try to choose such $$$a$$$ that $$$d$$$ will have $$$n$$$ digits.
At first, we can make the first digit of $$$d$$$ not equal to $$$0$$$ by setting $$$1$$$ to the first digit of $$$a$$$. Now we say that $$$d$$$ doesn't have leading zeroes. In this case, more digits $$$d$$$ has — the larger $$$d$$$ is. It turns out, we can always construct $$$d$$$ of length $$$n$$$ if we make each consecutive pair of digits different.
In other words, we want to select $$$a_i$$$ in order to make $$$a_{i-1} + b_{i-1} \neq a_{i} + b_{i}$$$ for all $$$i > 1$$$. Since we want to maximize $$$a_{i} + b_{i}$$$, if $$$a_{i} = 1$$$ satisfies $$$a_{i-1} + b_{i-1} \neq a_i + b_i$$$ we take $$$a_{i} = 1$$$. Otherwise, $$$a_{i} = 0$$$ satisfies this condition.
Time complexity is $$$\mathcal{O}(n)$$$.