AT_agc045_a [AGC045A] Xor Battle

[problemUrl]: https://atcoder.jp/contests/agc045/tasks/agc045_a $ 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` と出力せよ． 各テストケースごとに改行せよ．

### 制約 - $ 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 $ にできます．