给定一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$(仅由 $$$0$$$ 和 $$$1$$$ 组成的字符串)。如果存在长度为 $$$n$$$ 且包含 $$$x$$$ 的二进制字符串 $$$x$$$ ,则数字 $$$x$$$ 是好的,这样如果每个符号 $$$s_i$$$ 被替换为 $$$s_i \oplus l_i$$$ (其中 $$$\oplus$$$ 表示按位异或运算),那么字符串 $$$s$$$ 就成为回文。
您需要输出长度为 $$$n+1$$$ 的二进制字符串 $$$t$$$,其中 $$$t_i$$$ ($$$0 \leq i \leq n$$$) 等于 $$$1$$$ 如果数字 $$$i$$$ 是好的,否则 $$$0$$$ 。
回文是从左到右读取与从右到左读取相同的字符串。例如,01010、1111、0110 是回文。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。
每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一行,其中包含长度为 $$$n+1$$$ 的二进制字符串 $$$t$$$ - 问题的答案。
示例
输入 #1
5 6 101011 5 00000 9 100100011 3 100 1 1
输出 #1
0010100 111111 0011111100 0110 11
注意
考虑第一个例子。
- $$$t_2 = 1$$$ 因为我们可以选择 $$$l = $$$ 010100,那么字符串 $$$s$$$ 就变成了 111111,这是一个回文。
- $$$t_4 = 1$$$ 因为我们可以选择 $$$l = $$$ 101011。
- 可以证明,对于所有其他$$$i$$$,没有答案,因此剩下的符号是$$$0$$$。