CF1474A.Puzzle From the Future

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 \gt 21$, $012 \lt 101$, $021 = 21$ and so on.

2022 年，Mike 找到了两个长度为 $n$ 的二进制整数 $a$ 和 $b$（即它们仅由数字 $0$ 和 $1$ 组成），且允许有前导零。为了不忘记它们，他希望按如下方式构造一个整数 $d$：

• 他先将 $a$ 和 $b$ 进行无进位的按位加法，得到整数 $c$；因此 $c$ 中可能包含一个或多个数字 $2$。例如，$0110$ 与 $1101$ 的无进位按位加法结果为 $1211$；又如，$011000$ 与 $011000$ 的无进位按位加法结果为 $022000$；
• 然后 Mike 将 $c$ 中所有相邻且相等的数字替换为单个该数字，从而得到 $d$。在上述例子中，该操作将 $1211$ 变为 $121$，将 $022000$ 变为 $020$（因此 $d$ 中不再含有相邻相等的数字）。

不幸的是，Mike 在计算出 $d$ 之前就丢失了整数 $a$。现在，为了让他振作起来，你希望找出任意一个长度为 $n$ 的二进制整数 $a$，使得最终得到的 $d$ 作为整数时尽可能大。

此处“尽可能大”是指按通常的十进制整数大小比较：例如 $102 > 21$，$012 < 101$，$021 = 21$，等等。

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

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）—— 测试用例的数量。

每个测试用例的第一行包含整数 $n$（$1 \leq n \leq 10^5$）—— 数组 $a$ 和 $b$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的二进制整数 $b$。该整数 $b$ 仅由数字 $0$ 和 $1$ 组成。

保证所有 $t$ 个测试用例的 $n$ 值之和不超过 $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$.

对每个测试用例，输出一个长度为 $n$ 的二进制整数 $a$。注意，$a$ 或 $b$ 可能含有前导零，但它们的长度必须均为 $n$。

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

We can show that answer $a = 110$ is optimal and $d = 121$ is maximum possible.

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

在第一个测试用例中，$b = 0$，选择 $a = 1$ 可得结果 $d = 1$。

在第二个测试用例中，$b = 011$，因此：

• 若选择 $a = 000$，则 $c = 011$，故 $d = 01$；
• 若选择 $a = 111$，则 $c = 122$，故 $d = 12$；
• 若选择 $a = 010$，可得 $d = 021$；
• 若选择 $a = 110$，可得 $d = 121$。

可以证明，最优解为 $a = 110$，此时 $d = 121$ 是可能的最大值。

在第三个测试用例中，$b = 110$。若选择 $a = 100$，可得 $d = 210$，这是可能的最大 $d$ 值。

在第四个测试用例中，$b = 111000$。若选择 $a = 101101$，可得 $d = 212101$，这是可能的最大 $d$ 值。

在第五个测试用例中，$b = 001011$。若选择 $a = 101110$，可得 $d = 102121$，这是可能的最大 $d$ 值。