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:
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
enum = enumerate
inf = 1001001002002002002

import random

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

def gcd(a: int, b: int):
	while b: a, b = b, a%b
	return a

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	#exit(0)

def sol(N,vA,S):
	sZ = set({0,})
	for a,c in zip(vA[::-1],S[::-1]):
		v = a
		for z in reversed(sorted(list(sZ))):
			v = min(v, v^z)
			#if not N: print(z,v)##
		if c=="0":
			sZ |= {v,}
		elif v not in sZ:
			sZ = set({})
			break
		#else:
		#	pass	# sZ = sZ
		#if not N: print(sZ)##
	
	res = 1
	if sZ:
		res = 0
	
	#print(sZ)###
	print(res)


def main():
	T, = linput()
	for _ in "*"*T:
		N, = linput()
		vA = linput()
		S, = linput(str)
		sol(N, vA, S)

def ran():
	N = 200
	#N=6
	vRan = [random.randint(1,10) for _ in "*"*N]
	S = "".join(str(random.randint(0,1)) for _ in "*"*N)
	#print(max(vRan))#
	#vRan = [5, 7, 7, 3, 1, 7]###
	#S = "111000"###
	print(vRan,S)
	sol(N=0, vA=vRan, S=S)
	exit(0)
	
if __name__ == "__main__":
	#ran()
	main()