← 返回题目列表

Codeforces · 1474/A

A. 未来之谜

中文机器翻译题面 查看原题

在 $$$2022$$$ 年,Mike 发现了两个长度为 $$$n$$$ 的二进制整数 $$$a$$$ 和 $$$b$$$(它们都仅由数字 $$$0$$$ 和 $$$1$$$ 书写),并且可以有前导零。为了不忘记它们,他想通过以下方式构造整数$$$d$$$:

- 他创建了一个整数 $$$c$$$ 作为 $$$a$$$ 和 $$$b$$$ 按位求和的结果,而不传输进位,因此 $$$c$$$ 可能有一个或多个 $$$2$$$-s。例如$$$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$$$ 等等。

输入

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

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

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

保证所有$$$t$$$测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,输出一个长度为 $$$n$$$ 的二进制整数 $$$a$$$。请注意,$$$a$$$ 或$$$b$$$ 可以有前导零,但必须具有相同的长度$$$n$$$。

示例

输入 #1

5
1
0
3
011
3
110
6
111000
6
001011

输出 #1

1
110
100
101101
101110

注意

在第一个测试用例中,$$$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$$$。

在第三个测试用例中,$$$b = 110$$$。如果您选择 $$$a = 100$$$,您将得到 $$$d = 210$$$,这是可能的最大值 $$$d$$$。

在第四个测试用例中,$$$b = 111000$$$。如果您选择 $$$a = 101101$$$,您将得到 $$$d = 212101$$$,并且它是可能的最大值 $$$d$$$。

在第五个测试用例中,$$$b = 001011$$$。如果您选择 $$$a = 101110$$$,您将得到 $$$d = 102121$$$,并且它是可能的最大值 $$$d$$$。