题目描述

有 $2$ 个人，编号分别为 $0$ 和 $1$。还有一个初始值为 $0$ 的变量 $x$。接下来这两个人要进行一个游戏。游戏共进行 $N$ 轮，在第 $i$ 轮（$1 \leq i \leq N$）中，将进行如下操作：

• 编号为 $S_i$ 的人可以选择以下两种操作之一：
  • 用 $x \oplus A_i$ 替换 $x$。这里 $\oplus$ 表示按位异或运算。
  • 什么都不做。

编号为 $0$ 的人的目标是让最终 $x=0$，而编号为 $1$ 的人的目标是让最终 $x \neq 0$。

请判断当两个人都采取最优策略时，最终 $x$ 是否等于 $0$。

对于每组输入，请回答 $T$ 个测试用例。

输入格式

输入从标准输入读入。输入的第一行为：

$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
0
0

说明/提示

限制

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

样例解释 1

对于第 $1$ 个测试用例，如果编号为 $1$ 的人将 $x$ 替换为 $0 \oplus 1=1$，无论编号为 $0$ 的人怎么操作，最终 $x \neq 0$。对于第 $2$ 个测试用例，无论编号为 $1$ 的人做哪种操作，只要编号为 $0$ 的人采取合适的操作，都可以让 $x=0$。

由 ChatGPT 4.1 翻译