题目描述

$2$ 人の人がおり，$0$ と $1$ の番号がついています． また，$0$ で初期化された変数 $x$ があります． これから $2$ 人はゲームを行います． ゲームは $N$ ラウンドからなり，$i$ 回目 ($1\ \leq\ i\ \leq\ N$) のラウンドでは，次の操作が行われます．

• 人 $S_i$ が以下のいずれかの操作をする．
  • $x$ を $x\ \oplus\ A_i$ で置き換える．ただしここで $\oplus$ はbitごとの排他的論理和を表す．
  • 何もしない．

人 $0$ の目標は，最終的に $x=0$ にすることで，逆に人 $1$ の目標は，最終的に $x\ \neq\ 0$ にすることです．

$2$ 人が最適に行動する時，最終的に $x$ が $0$ になるかどうかを判定してください．

$1$ つの入力につき，$T$ 個のテストケースに答えてください．

输入格式

入力は以下の形式で標準入力から与えられる． 入力の $1$ 行目は以下のとおりである．

$T$

そして，$T$ 個のテストケースが続く． これらはそれぞれ以下の形式で与えられる．

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

输出格式

各テストケースについて，最終的に $x=0$ となる場合は 0，そうでない場合は 1 と出力せよ． 各テストケースごとに改行せよ．

题目大意

给定一个长为 $n$ 的数组 $A$ 和同样长度的 $01$ 串 $S$，编号为 $0$ 和 $1$ 的两个人将要围绕着一个初始为 $0$ 的数做博弈。

博弈按照数组的顺序进行。当进行到第 $i$ 轮的时候，轮到编号为 $S_i$ 的人开始行动。
他可以选择把当前的 $x$ 按位异或上 $A_i$，也可以什么都不做。

$0$ 的目标是使得 $x$ 最终变成 $0$，而 $1$ 的目标反之，即让 $x$ 最终不为 $0$。

两人总共进行 $T$ 局游戏，你需要对于每一局游戏输出两人中的哪一个有必胜策略。

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$ の文字列
• 入力される数は全て整数である．

Sample Explanation 1

$1$ つ目のテストケースでは，人 $1$ が $x$ を $0\ \oplus\ 1=1$ で置き換えると，人 $0$ の操作に依らず，最終的に $x\ \neq\ 0$ になります． $2$ つ目のテストケースでは，人 $1$ がどちらの操作を行っても，人 $0$ が適切な操作をすれば $x=0$ にできます．