配点 : $400$ 点

問題文

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

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

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

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

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

制約

• $1 \leq T \leq 100$
• $1 \leq N \leq 200$
• $1 \leq A_i \leq 10^{18}$
• $S$ は 0 と 1 のみからなる長さ $N$ の文字列
• 入力される数は全て整数である．

入力

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

$T$

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

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

$S$

出力

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

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

1
0
0

$1$ つ目のテストケースでは，人 $1$ が $x$ を $0 \oplus 1=1$ で置き換えると，人 $0$ の操作に依らず，最終的に $x \neq 0$ になります．

$2$ つ目のテストケースでは，人 $1$ がどちらの操作を行っても，人 $0$ が適切な操作をすれば $x=0$ にできます．