#agc045a. [agc045_a]Xor Battle

[agc045_a]Xor Battle

Problem Statement

There are two persons, numbered 00 and 11, and a variable xx whose initial value is 00. The two persons now play a game. The game is played in NN rounds. The following should be done in the ii-th round (1leqileqN1 \\leq i \\leq N):

  • Person SiS_i does one of the following:
    • Replace xx with xoplusAix \\oplus A_i, where oplus\\oplus represents bitwise XOR.
    • Do nothing.

Person 00 aims to have x=0x=0 at the end of the game, while Person 11 aims to have xneq0x \\neq 0 at the end of the game.

Determine whether xx becomes 00 at the end of the game when the two persons play optimally.

Solve TT test cases for each input file.

Constraints

  • 1leqTleq1001 \\leq T \\leq 100
  • 1leqNleq2001 \\leq N \\leq 200
  • 1leqAileq10181 \\leq A_i \\leq 10^{18}
  • SS is a string of length NN consisting of 0 and 1.
  • All numbers in input are integers.

Input

Input is given from Standard Input in the following format. The first line is as follows:

TT

Then, TT test cases follow. Each test case is given in the following format:

NN A1A_1 A2A_2 cdots\\cdots ANA_N SS

Output

For each test case, print a line containing 0 if xx becomes 00 at the end of the game, and 1 otherwise.


Sample Input 1

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

Sample Output 1

1
0
0

In the first test case, if Person 11 replaces xx with 0oplus1=10 \\oplus 1=1, we surely have xneq0x \\neq 0 at the end of the game, regardless of the choice of Person 00.

In the second test case, regardless of the choice of Person 11, Person 00 can make x=0x=0 with a suitable choice.