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

* Person S_i does one of the following:
* Replace x with x \oplus A_i, where \oplus represents bitwise XOR.
* Do nothing.



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

Determine whether x becomes 0 at the end of the game when the two persons play optimally.

Solve T test cases for each input file.

Constraints

* 1 \leq T \leq 100
* 1 \leq N \leq 200
* 1 \leq A_i \leq 10^{18}
* S is a string of length N 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:


T


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


N
A_1 A_2 \cdots A_N
S


Output

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

Example

Input

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


Output

1
0
0

Solution (in PYTHON3):

Solution:
from heapq import heappush, heappop


def calcSpace():
    H = []
    hpush = lambda x: heappush(H, -x)
    hpop = lambda: -heappop(H)
    for x in X:
        hpush(x)
    
    E = [0] * 60
    while H:
        x = hpop()
        b = x.bit_length() - 1
        if E[b]:
            x ^= E[b]
            if x: hpush(x)
        else:
            E[b] = x
    
    return E
    
def chk(y):
    y0 = y
    for i in range(60)[::-1]:
        if y >> i & 1:
            if V[i]:
                y ^= V[i]
                # print("chk", y0, "OK", V)
                if y == 0: return 1
            else:
                return 0

def chk_all():
    for y in Y:
        if chk(y) == 0:
            return 1
            break
    else:
        return 0
    
T = int(input())
for _ in range(T):
    N = int(input())
    A = [int(a) for a in input().split()]
    S = [int(a) for a in input()]
    
    if 0:
        print("N =", N)
        print("A =", A)
        print("S =", S)
    
    X = []
    Y = []
    i = N - 1
    ans = 0
    while i >= 0:
        while i >= 0:
            if S[i]: break
            X.append(A[i])
            i -= 1
        while i >= 0:
            if S[i] == 0: break
            Y.append(A[i])
            i -= 1

            V = calcSpace()
            # print("X =", X)
            # print("Y =", Y)
            # print("V =", V)
            if chk_all():
                ans = 1
                i = -1
    print(ans)