問題文

$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 \\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 と出力せよ． 各テストケースごとに改行せよ．

入力例 1

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

出力例 1

1
0
0

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

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