A1828.构造数字

$AC$ 狗发现了两个长度为 $n$ 的二进制整数 $a$ 和 $b$（这两个整数每一位都只能由数字 $0$ 和 $1$ 组成），它们可以有前导零。

为了不忘记这两个整数，它想用以下方式构造整数 $d$：

• 将 $a$ 和 $b$ 逐位相加，但不发生进位得到 $c$。例如：0110 加 1101 的结果为 1211；011000 加 011000 的结果为 022000。
• 将 $c$ 中连续的相等数字替换成一个数字，得到 $d$。
  例如：1211 变为 121，022000 变为 020。

不幸的是，$AC$ 狗在计算出 $d$ 之间就忘记了 $a$。现在为了让 $AC$ 狗高兴起来，你需要找到一个长度为 $n$ 的二进制数 $a$，使得 $a$ 和 $b$ 构造出的 $d$ 最大。

（在比较大小时：$102>21$, $012<101$, $021=21$）

第一行包含一个整数 $T$ ($1 \le T \le 100$) — 表示测试用例的数量。

每个测试用例的第一行包含整数 $n$ ($1 \le n \le 10^5$) — 表示 $b$ 的长度。

每个测试用例的第二行包含$b$。

对于每个测试用例输出 $a$，有前导 $0$ 的话也需要输出。

在第一个测试用例中，$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$ 是最大的。

在第三个测试用例中，$b = 110$ ，$a = 100$ 时 $d = 210$ 是最大的。

在第四个测试用例中，$b = 111000$ ，$a = 101101$ 时 $d = 212101$ 是最大的。

在第五个测试用例中，$b = 001011$ ，$a = 101110$ 时 $d = 102121$ 是最大的。