问题 6863 --二进制谜题

6863: 二进制谜题★★

时间限制: 1 Sec  内存限制: 256 MB
提交: 18  解决: 10
[提交][状态][命题人:]

题目描述

有长度为 n 的两个二进制整数 a 和 b(可以有前导零),用下面的方法构造整数 d:

设整数 c 作为 a 和 b 按位相加的结果,例如 0110 和 1101 的相加结果是 1211,011000 和 011000 相加是 022000;然后,将 c 中连续的相同数字只保留一个,从而得到 d(例如 1211 变为 121,022000 变为 020)

现在给定 b,请找出长度为 n 的任意二进制整数 a,使得 d 尽可能大。

(尽可能大是指 102>21,012<101,021=21 以此类推)

输入

第一行:整数 t(1 ≤ t ≤ 1000)- 样例数量

每个样例的第一行:整数 n(1 ≤ n ≤ 105)- a 和 b 的位数

每个样例的第二行:二进制数 b

所有样例中 n 的总和不超过 105

输出

对于每个样例,输出二进制数 a
样例输入
Copy
5
1
0
3
011
3
110
6
111000
6
001011
样例输出
Copy
1
110
100
101101
101110

提示

来源

[提交][状态]