题目描述

有两个人，编号为 $0$ 和 $1$，还有一个变量 $x$，初始值为 $0$。这两个人现在玩一个游戏。游戏共进行 $N$ 轮。在第 $i$ 轮中 ($1 \\leq i \\leq N$)，应该做以下操作之一：

• 人 $S_i$ 执行以下操作之一：
  • 将 $x$ 替换为 $x \\oplus A_i$，其中 $\\oplus$ 表示按位异或。
  • 不进行任何操作。

第 $0$ 个人的目标是在游戏结束时使 $x=0$，而第 $1$ 个人的目标是在游戏结束时使 $x \\neq 0$。

判断当两个人都做出最优选择时，$x$ 是否会在游戏结束时变为 $0$。

对于每个输入文件，解决 $T$ 个测试用例。

约束条件

• $1 \\leq T \\leq 100$
• $1 \\leq N \\leq 200$
• $1 \\leq A_i \\leq 10^{18}$
• $S$ 是一个长度为 $N$ 的由 0 和 1 组成的字符串。
• 输入中的所有数字都是整数。

输入

输入以标准输入格式给出，格式如下所示。第一行如下：

$T$

接下来，按照如下格式给出 $T$ 个测试用例：

$N$ $A_1$ $A_2$ $\\cdots$ $A_N$ $S$

输出

对于每个测试用例，如果 $x$ 在游戏结束时变为 $0$，则打印一行包含 0，否则打印 1。

示例输入 1

3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000

示例输出 1

1
0
0

在第一个测试用例中，如果第 $1$ 个人将 $x$ 替换为 $0 \\oplus 1=1$，则无论第 $0$ 个人的选择如何，我们都有 $x \\neq 0$。

在第二个测试用例中，无论第 $1$ 个人的选择如何，第 $0$ 个人都可以通过适当的选择使得 $x=0$。