题目描述

对于两个长度为 $n$ 的二进制整数 $a$,$b$，通过以下方式构造出整数 $d$：

1. 将 $a$ 和 $b$ 按位相加但不进行进位运算，得到一个整数 $c$，因此 $c$ 中可能有 $2$。例如将 $0110$ 与 $1101$ 按位相加的结果是 $1211$。

2. 将 $c$ 中相同且连续的数字替换为一位，得到 $d$。例如将 $022000$ 变成 $020$（因此，$d$ 没有相同且连续的数字）。

现在，给你 $b$，求一个 $a$ 使得 $d$ 最大。

输入格式

第一行为测试数据组数 $t(1 \leq t \leq 1000)$

每个测试数据包含两行。

第一行为一个整数 $n(1 \leq n \leq 10^5)$，表示二进制数 $a$,$b$ 的长度。

第二行一个长度为 $n$ 的二进制整数 $b$。

输出格式

对于每一个测试数据，输出一个长度为 $n$ 的二进制整数 $a$，使得通过 $a$,$b$ 构造出的整数 $d$ 最大。

by uid=390770

样例

5
1
0
3
011
3
110
6
111000
6
001011

1
110
100
101101
101110