AtCoder Grand Contest 045 - Xor Battle

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

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def slv(n, a, s):
	base = [0]
	for i in range(n - 1, -1, -1):
		v = a[i]
		for j in sorted(base, reverse=True):
			v = min(v, j ^ v)
		if v == 0:
			pass
		else:
			if s[i] == '0':
				base.append(v)
			if s[i] == '1':
				return 1
	if base:
		return 0
	return 1
t = int(input())
n = []
a = []
s = []
for _ in range(t):
	n.append(int(input()))
	a.append(list(map(int, input().split())))
	s.append(input())
for i in range(t):
	print(slv(n[i], a[i], s[i]))


import sys
iim = lambda : map(int, sys.stdin.readline().rstrip().split())

def f(a, s, n):
	if s[-1] == '1':
		return 1
	X = max(a).bit_length()
	B = [None] * X
	for i in range(n - 1, -1, -1):
		(ai, si) = (a[i], s[i])
		if si == '0':
			while True:
				x = ai.bit_length() - 1
				if B[x] == ai:
					break
				elif B[x] == None:
					B[x] = ai
					X -= 1
					if X == 0:
						return 0
					break
				ai ^= B[x]
		else:
			while True:
				x = ai.bit_length() - 1
				if B[x] == ai:
					break
				elif B[x] == None:
					return 1
				ai ^= B[x]
	return 0

def resolve():
	T = int(input())
	ans = []
	for i in range(T):
		N = int(input())
		A = list(iim())
		S = input()
		ans.append(f(A, S, N))
	print(*ans, sep='\n')
resolve()


def solve():
	dp = [0]
	for (a, s) in zip(A[::-1], S[::-1]):
		x = a
		for y in dp:
			x = min(x, x ^ y)
		if s == '0':
			if x:
				dp.append(x)
		elif x:
			return 1
	return 0
t = int(input())
for i in range(t):
	n = int(input())
	(*A,) = map(int, input().split())
	S = input()
	print(solve())


M = 60

def topbit(n):
	res = -1
	for i in range(M, -1, -1):
		if n & 2 ** i != 0:
			res = i
			break
	return res

def solve():
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	base = {}
	ans = '0'
	for i in range(N - 1, -1, -1):
		if S[i] == '0':
			s = A[i]
			while s != 0:
				n = topbit(s)
				if n not in base:
					base[n] = s
					break
				else:
					s ^= base[n]
		else:
			s = A[i]
			while s != 0:
				n = topbit(s)
				if n not in base:
					ans = '1'
					break
				else:
					s ^= base[n]
	print(ans)
T = int(input())
for t in range(T):
	solve()


T = int(input())
for _ in range(T):
	N = int(input())
	As = list(map(int, input().split()))
	S = list(input())
	mine = [0] * 61
	for (a, s) in reversed(list(zip(As, S))):
		bl = a.bit_length()
		if s == '0':
			while bl > 0:
				if a >> bl - 1 & 1:
					if mine[bl] == 0:
						mine[bl] = a
						break
					a ^= mine[bl]
				bl -= 1
		else:
			while bl > 0:
				if a >> bl - 1 & 1:
					if mine[bl] == 0:
						print(1)
						break
					a ^= mine[bl]
				bl -= 1
			else:
				continue
			break
	else:
		print(0)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	list0 = [0] * 64
	ans = 0
	for (a, s) in zip(reversed(A), reversed(S)):
		while a:
			b = a.bit_length() - 1
			if list0[b]:
				a ^= list0[b]
			else:
				if s == '1':
					ans = 1
				else:
					list0[b] = a
				break
		if ans:
			break
	print(ans)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	base = []
	for i in range(N - 1, -1, -1):
		a = A[i]
		for b in base:
			test = a ^ b
			if a > test:
				a = test
		if a != 0:
			if S[i] == '1':
				print('1')
				break
			else:
				base.append(a)
	else:
		print('0')


import bisect
from itertools import accumulate
T = int(input())
for _ in range(T):
	N = int(input())
	As = list(map(int, input().split()))
	S = input()
	possible_xor = []
	if S[-1] == '1':
		print(1)
		continue
	flg = True
	for (c, A) in reversed(list(zip(S, As))):
		if c == '0':
			for xor in possible_xor[::-1]:
				if A.bit_length() == xor.bit_length():
					A ^= xor
				elif A > xor:
					break
			possible_xor.insert(bisect.bisect_left(possible_xor, A), A)
		else:
			for xor in possible_xor[::-1]:
				if A.bit_length() == xor.bit_length():
					A ^= xor
			if A != 0:
				flg = False
				break
	if flg:
		print(0)
	else:
		print(1)


def solve(N, A, S):
	B = [0] * 64
	for (a, s) in zip(reversed(A), reversed(S)):
		if s == '1':
			while a:
				n = a.bit_length() - 1
				if B[n] == 0:
					return 1
				a ^= B[n]
		else:
			while a:
				n = a.bit_length() - 1
				if B[n] == 0:
					B[n] = a
					break
				a ^= B[n]
	return 0

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = list(map(int, input().split()))
		S = input()
		print(solve(N, A, S))
main()


def solve(N, A, S):
	bit = [0] * 64
	for i in range(N - 1, -1, -1):
		Ai = A[i]
		Si = S[i]
		while Ai:
			n = Ai.bit_length() - 1
			if bit[n] == 0 and Si == '1':
				return 1
			elif bit[n] == 0 and Si == '0':
				bit[n] = Ai
				break
			Ai ^= bit[n]
	return 0
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	print(solve(N, A, S))


T = int(input())
for _ in [0] * T:
	N = int(input())
	(*A,) = map(int, input().split())
	S = input()
	B = []
	ans = 0
	for (s, a) in zip(S[::-1], A[::-1]):
		if s == '0':
			B.append(a)
		else:
			C = B[:]
			for i in range(64):
				for b in C:
					if b >> i & 1 == 1:
						break
				else:
					continue
				if a >> i & 1 == 1:
					a ^= b
				for (j, c) in enumerate(C):
					if c >> i & 1 == 1:
						C[j] ^= b
			if a != 0:
				ans = 1
				break
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	if S[-1] == '1':
		print(1)
		continue
	list0 = [0] * 64
	for (a, s) in zip(A[::-1], S[::-1]):
		blen = a.bit_length()
		for i in range(blen, 0, -1):
			if a.bit_length() < i:
				continue
			if list0[i - 1]:
				a ^= list0[i - 1]
				if a == 0:
					break
		else:
			if s == '1':
				ans = 1
				break
			else:
				list0[a.bit_length() - 1] = a
	else:
		ans = 0
	print(ans)


def xor_gauss_jordan(A):
	cnt_row = len(A)
	cnt_col = len(bin(max(A))[2:])
	rank = 0
	for col in range(cnt_col):
		pivot = -1
		for row in range(rank, cnt_row):
			if A[row] & 2 ** (cnt_col - col - 1):
				pivot = row
				break
		if pivot == -1:
			continue
		(A[pivot], A[rank]) = (A[rank], A[pivot])
		A_rank = A[rank]
		for row in range(cnt_row):
			if row != rank and A[row] & 2 ** (cnt_col - col - 1):
				A[row] ^= A[rank]
		rank += 1
	return A
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	hand = [0]
	flag = False
	for i in range(n)[::-1]:
		val = a[i]
		if s[i] == '1':
			hand.sort(reverse=True)
			for num in hand:
				if val.bit_length() == num.bit_length():
					val ^= num
			if val != 0:
				flag = True
		else:
			hand.append(val)
			hand = xor_gauss_jordan(hand)
	if flag:
		print(1)
	else:
		print(0)


T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	S = input()
	B = []
	ans = 0
	for (a, s) in zip(reversed(A), reversed(S)):
		for b in B:
			a = a if a < a ^ b else a ^ b
		if a:
			if s == '1':
				ans = 1
				break
			B.append(a)
	print(ans)


import sys
from functools import reduce
from operator import or_
iim = lambda : map(int, sys.stdin.readline().rstrip().split())
X = 60

def f(a, s, n):
	if s[-1] == '1':
		return 1
	y = bin(reduce(or_, a)).count('1')
	B = [None] * X
	for i in range(n - 1, -1, -1):
		(ai, si) = (a[i], s[i])
		if si == '0':
			while True:
				x = ai.bit_length() - 1
				if B[x] == ai:
					break
				elif B[x] == None:
					B[x] = ai
					y -= 1
					if y == 0:
						return 0
					break
				ai ^= B[x]
		else:
			while True:
				x = ai.bit_length() - 1
				if B[x] == ai:
					break
				elif B[x] == None:
					return 1
				ai ^= B[x]
	return 0

def resolve():
	T = int(input())
	ans = []
	for i in range(T):
		N = int(input())
		A = list(iim())
		S = input()
		ans.append(f(A, S, N))
	print(*ans, sep='\n')
resolve()


def main():
	t = int(input())
	for _ in range(t):
		(nn, aa, s, r, mm) = (int(input()), list(map(int, input().split())), input(), 0, [])
		for ii in range(nn - 1, -1, -1):
			ai = aa[ii]
			mm += [[ai >> jj & 1 for jj in range(64)]]
			(n, i, j) = (r + 1, 0, 0)
			while i < n and j < 64:
				if mm[i][j] == 1 and mm[n - 1][j] == 0:
					i += 1
					j += 1
					continue
				if mm[i][j] == 0:
					if mm[n - 1][j] != 0:
						for l in range(j, 64):
							mm[i][l] ^= mm[n - 1][l]
					else:
						j += 1
						continue
				M2 = mm[i]
				for k in range(i + 1, n):
					M3 = mm[k][j]
					mm[k][j] = 0
					for l in range(j + 1, 64):
						mm[k][l] ^= M3 * M2[l]
				i += 1
				j += 1
			if s[ii] == '0':
				if i > r:
					r += 1
				else:
					mm.pop()
			else:
				mm.pop()
				if i > r:
					print(1)
					break
		else:
			print(0)
main()


import sys
input = sys.stdin.readline
import math
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
MOD = 10 ** 9 + 7
INF = float('inf')

def I():
	return int(input().strip())

def S():
	return input().strip()

def IL():
	return list(map(int, input().split()))

def SL():
	return list(map(str, input().split()))

def ILs(n):
	return list((int(input()) for _ in range(n)))

def SLs(n):
	return list((input().strip() for _ in range(n)))

def ILL(n):
	return [list(map(int, input().split())) for _ in range(n)]

def SLL(n):
	return [list(map(str, input().split())) for _ in range(n)]

def P(arg):
	print(arg)
	return

def Y():
	print('Yes')
	return

def N():
	print('No')
	return

def E():
	exit()

def PE(arg):
	print(arg)
	exit()

def YE():
	print('Yes')
	exit()

def NE():
	print('No')
	exit()

def DD(arg):
	return defaultdict(arg)

def inv(n):
	return pow(n, MOD - 2, MOD)
kaijo_memo = []

def kaijo(n):
	if len(kaijo_memo) > n:
		return kaijo_memo[n]
	if len(kaijo_memo) == 0:
		kaijo_memo.append(1)
	while len(kaijo_memo) <= n:
		kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
	return kaijo_memo[n]
gyaku_kaijo_memo = []

def gyaku_kaijo(n):
	if len(gyaku_kaijo_memo) > n:
		return gyaku_kaijo_memo[n]
	if len(gyaku_kaijo_memo) == 0:
		gyaku_kaijo_memo.append(1)
	while len(gyaku_kaijo_memo) <= n:
		gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD)
	return gyaku_kaijo_memo[n]

def nCr(n, r):
	if n == r:
		return 1
	if n < r or r < 0:
		return 0
	ret = 1
	ret = ret * kaijo(n) % MOD
	ret = ret * gyaku_kaijo(r) % MOD
	ret = ret * gyaku_kaijo(n - r) % MOD
	return ret

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

def make_divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	return divisors

def make_primes(N):
	max = int(math.sqrt(N))
	seachList = [i for i in range(2, N + 1)]
	primeNum = []
	while seachList[0] <= max:
		primeNum.append(seachList[0])
		tmp = seachList[0]
		seachList = [i for i in seachList if i % tmp != 0]
	primeNum.extend(seachList)
	return primeNum

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

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

def count_bit(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count

def base_10_to_n(X, n):
	if X // n:
		return base_10_to_n(X // n, n) + [X % n]
	return [X % n]

def base_n_to_10(X, n):
	return sum((int(str(X)[-i - 1]) * n ** i for i in range(len(str(X)))))

def int_log(n, a):
	count = 0
	while n >= a:
		n //= a
		count += 1
	return count

def kitei(SET, b):
	for k in SET:
		if k ^ b < b:
			b = k ^ b
	return {b}

def can_made_by(SET, b):
	if SET == set():
		return False
	for k in SET:
		if k ^ b < b:
			b = k ^ b
	if b:
		return False
	else:
		return True

def solve():
	N = I()
	A = IL()
	S_ = S()
	dp = [None for i in range(N + 1)]
	dp[N] = {0}
	for i in range(N)[::-1]:
		if S_[i] == '0':
			if dp[i + 1]:
				dp[i] = dp[i + 1] | kitei(dp[i + 1], A[i])
			else:
				dp[i] = dp[i + 1]
		elif can_made_by(dp[i + 1], A[i]):
			dp[i] = dp[i + 1]
		else:
			dp[i] = set()
	if dp[0] == set():
		print(1)
	else:
		print(0)
T = I()
for _ in range(T):
	solve()


import sys
from copy import deepcopy

def canMake(k, Nums):
	L = len(Nums)
	index = 0
	bit = []
	for i in reversed(range(60)):
		flag = 0
		for j in range(index, L):
			if Nums[j] & 1 << i == 1 << i:
				flag = 1
				(Nums[index], Nums[j]) = (Nums[j], Nums[index])
				bit.append(i)
				break
		if flag == 1:
			for j in range(L):
				if Nums[j] & 1 << i == 1 << i and index != j:
					Nums[j] ^= Nums[index]
		if flag == 1:
			index += 1
	ans = 0
	for i in range(60):
		if k & 1 << i == 1 << i:
			if i in bit:
				ans ^= Nums[bit.index(i)]
	if ans == k:
		return True
	else:
		return False

def solve():
	input = sys.stdin.readline
	T = int(input())
	Ans = [0] * T
	for t in range(T):
		N = int(input())
		A = [int(a) for a in input().split()]
		S = input().strip('\n')
		used = []
		for i in reversed(range(N)):
			if S[i] == '0':
				used.append(A[i])
			else:
				compare = deepcopy(used)
				if not canMake(A[i], compare):
					Ans[t] = 1
					break
	print(*Ans, sep='\n')
	return 0
solve()


def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():
	mod = 10 ** 9 + 7
	T = I()
	M = 60

	def pipo(x):
		cnt = 0
		for i in range(M):
			if x == 0:
				return cnt
			else:
				x = x // 2
				cnt += 1
	for _ in range(T):
		N = I()
		A = LI()
		S = list(input())
		Vec = []
		flag = 1
		for i in range(N - 1, -1, -1):
			if S[i] == '0':
				now = A[i]
				p = pipo(A[i])
				for v in Vec:
					if v[1] == p:
						now = now ^ v[0]
						p = pipo(now)
				if now != 0:
					Vec.append((now, pipo(now)))
					Vec.sort(reverse=True)
			else:
				now = A[i]
				for v in Vec:
					if v[1] == pipo(now):
						now = now ^ v[0]
				if now != 0:
					flag = 0
		if flag:
			print(0)
		else:
			print(1)
main()


import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():

	def calc():
		n = int(readline())
		a = list(map(int, readline().split()))
		s = input()
		b = [-1] * 61
		for i in range(n - 1, -1, -1):
			x = a[i]
			if s[i] == '0':
				l = x.bit_length()
				if b[l - 1] == -1:
					b[l - 1] = x
				else:
					while b[l - 1] != -1 and x > 0:
						x ^= b[l - 1]
						l = x.bit_length()
					if x != 0:
						b[l - 1] = x
			else:
				xb = format(x, 'b')[::-1]
				l = len(xb)
				cur = 0
				for j in range(l - 1, -1, -1):
					bit = int(xb[j])
					cur_bit = int(format(cur, 'b').zfill(l)[::-1][j])
					if bit ^ cur_bit == 1:
						if b[j] != -1:
							cur ^= b[j]
						else:
							return print(1)
		return print(0)
	t = int(readline())
	for _ in range(t):
		calc()
main()


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]
				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()
			if chk_all():
				ans = 1
				i = -1
	print(ans)


def f():
	n = int(input())
	A = list(map(int, input().split()))
	S = list(map(int, list(input())))
	basis = []
	for i in range(n - 1, -1, -1):
		(a, s) = (A[i], S[i])
		l = len(basis)
		for b in basis:
			a = min(a, a ^ b)
		if a:
			basis.append(a)
		if s and len(basis) != l:
			print(1)
			return
	print(0)
t = int(input())
for _ in range(t):
	f()


class F2n:

	def __init__(self, LIST):
		self.basis = []
		for ele in LIST:
			for vec in self.basis:
				ele = min(ele, vec ^ ele)
			if ele:
				self.basis.append(ele)

	def Add(self, ele):
		for vec in self.basis:
			ele = min(ele, ele ^ vec)
		if ele:
			self.basis.append(ele)
			return True
		else:
			return False

def solve():
	n = int(input())
	a = list(map(int, input().split()))[::-1]
	s = input()[::-1]
	h = F2n([])
	for i in range(n):
		if h.Add(a[i]):
			if s[i] == '1':
				print(1)
				return
	print(0)
t = int(input())
for _ in range(t):
	solve()


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	S = list(map(int, input()))
	for i in range(N - 1, -1, -1):
		ai = A[i]
		if ai == 0:
			continue
		top = ai.bit_length() - 1
		for j in range(i - 1, -1, -1):
			if A[j] >> top & 1:
				A[j] ^= ai
	for (a, c) in zip(A[::-1], S[::-1]):
		if c == 1 and a:
			break
	else:
		print('0')
		continue
	print('1')


def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = list(map(int, input().split()))
		S = input()
		L = max(A).bit_length()
		s = [0] * L

		def check(x):
			for i in range(L - 1, -1, -1):
				if (x >> i) % 2:
					x ^= s[i]
			return x == 0

		def update(x):
			for i in range(L - 1, -1, -1):
				if (x >> i) % 2:
					x ^= s[i]
			id = x.bit_length() - 1
			if id >= 0:
				s[id] = x
		res = 0
		for i in range(N - 1, -1, -1):
			k = int(S[i])
			if k:
				if check(A[i]):
					continue
				else:
					res = 1
					break
			else:
				update(A[i])
		print(res)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	check = True
	l = [0] * 61
	for i in range(n - 1, -1, -1):
		x = a[i]
		for j in range(60, -1, -1):
			if x & 1 << j:
				x ^= l[j]
		if s[i] == '0':
			if x:
				l[x.bit_length() - 1] = x
		elif x:
			print(1)
			check = False
			break
	if check:
		print(0)


import sys
read = sys.stdin.read
readline = sys.stdin.readline

def solve():

	def normalize(v, basis):
		for b in basis:
			if v > v ^ b:
				v ^= b
		return v
	(n,) = map(int, readline().split())
	(*a,) = map(int, readline().split())
	s = input()
	basis = []
	b0 = []
	for (e, si) in zip(a[::-1], s[::-1]):
		if si == '0':
			for b in basis:
				if e > e ^ b:
					e ^= b
			if e:
				basis.append(e)
		if si == '1':
			v = normalize(e, basis)
			if v != 0:
				print(1)
				return
	print(0)
	return
t = int(input())
for _ in range(t):
	solve()


import sys, queue, math, copy, itertools, bisect, collections, heapq
import random

def main():
	sys.setrecursionlimit(10 ** 7)
	INF = float('inf')
	MOD = 10 ** 9 + 7
	LI = lambda : [int(x) for x in sys.stdin.readline().split()]
	_LI = lambda : [int(x) - 1 for x in sys.stdin.readline().split()]
	NI = lambda : int(sys.stdin.readline())
	SI = lambda : sys.stdin.readline().rstrip()
	DD = ((1, 0), (0, 1), (-1, 0), (0, -1))
	T = NI()
	for _ in range(T):
		N = NI()
		A = LI()
		S = SI()
		base = [0] * 60
		for i in range(N - 1, -1, -1):
			x = A[i]
			if S[i] == '0':
				for j in range(60):
					if base[j] > 0 and x & 1 << j:
						x ^= base[j]
				for j in range(60):
					if base[j] == 0 and x & 1 << j:
						for k in range(60):
							if base[k] & 1 << j:
								base[k] ^= x
						base[j] = x
						break
			else:
				for j in range(60):
					if base[j] > 0 and x & 1 << j:
						x ^= base[j]
				if x > 0:
					print(1)
					break
		else:
			print(0)
main()


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def deepcopy(li):
	return [x[:] for x in li]

def gauss_jordan(A, extended=False):
	(N, M) = (len(A), max(A).bit_length())
	B = A[:]
	rank = 0
	res = []
	for col in range(M):
		if extended and col == M - 1:
			break
		pivot = -1
		for row in range(rank, N):
			if B[row] >> col & 1:
				pivot = row
				break
		if pivot == -1:
			continue
		(B[rank], B[pivot]) = (B[pivot], B[rank])
		for row in range(N):
			if row != rank and B[row] >> col & 1:
				B[row] ^= B[rank]
		res.append(col)
		rank += 1
	for row in range(rank, N):
		if B[row] >> M - 1 & 1:
			return (-1, [])
	return (rank, res)
for _ in range(INT()):
	N = INT()
	A = LIST()
	S = input()
	M = max(A).bit_length()
	mat = [0] * M
	collen = 1
	for i in range(N - 1, -1, -1):
		if S[i] == '0':
			for k in range(M):
				mat[k] |= (A[i] >> k & 1) << collen
			collen += 1
		else:
			cur = mat[:]
			for k in range(M):
				cur[k] |= (A[i] >> k & 1) << collen
			(rank, res) = gauss_jordan(cur, extended=True)
			if rank == -1:
				print(1)
				break
	else:
		print(0)


def solve():
	base = []
	for (a, s) in zip(A[::-1], S[::-1]):
		x = a
		for y in base:
			x = min(x, x ^ y)
		if x:
			if s == '0':
				base.append(x)
			else:
				return 1
	return 0
t = int(input())
for _ in range(t):
	n = int(input())
	(*A,) = map(int, input().split())
	S = input()
	print(solve())


from collections import defaultdict
itl = lambda : list(map(int, input().strip().split()))

def solve():
	N = int(input())
	nums = itl()
	S = input().strip()
	basis = []
	for i in range(N - 1, -1, -1):
		v = nums[i]
		for b in basis:
			v = min(v, v ^ b)
		if v:
			if S[i] == '1':
				return 1
			basis.append(v)
	return 0
T = int(input())
for _ in range(T):
	print(solve())


class VectorSpace01:

	def __init__(self):
		self.E = []

	def chk(self, n):
		for e in self.E:
			n = min(n, n ^ e)
		return 1 if n == 0 else 0

	def add(self, n):
		for e in self.E:
			n = min(n, n ^ e)
		if n:
			self.E.append(n)
		return 1 if n == 0 else 0

	def dimension(self):
		return len(self.E)
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()]
	vs = VectorSpace01()
	for i in range(N)[::-1]:
		a = vs.add(A[i])
		if S[i] and a == 0:
			print(1)
			break
	else:
		print(0)


printn = lambda x: print(x, end='')
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
ins = lambda : input().strip()
DBG = True
BIG = 10 ** 18

def ddprint(x):
	if DBG:
		print(x)

def cover0(c, d):
	m = len(c)
	for i in range(m):
		if c[i] == 0:
			continue
		k = -1
		for j in range(62):
			b = 1 << j
			if c[i] & b != 0:
				k = j
				break
		for j in range(i + 1, m):
			if c[j] & b != 0:
				c[j] ^= c[i]
		for j in range(len(d)):
			if d[j] & b != 0:
				d[j] ^= c[i]
	return sum(d) == 0
t = inn()
for tt in range(t):
	n = inn()
	a = inl()
	s = ins()
	top = n
	to0 = []
	to1 = []
	done = False
	while top > 0:
		prev0 = top
		while top > 0 and s[top - 1] == '0':
			top -= 1
		top0 = top
		to0.extend(a[top0:prev0])
		prev1 = top
		while top > 0 and s[top - 1] == '1':
			top -= 1
		top1 = top
		to1.extend(a[top1:prev1])
		cc = [x for x in to0]
		dd = [x for x in to1]
		if not cover0(cc, dd):
			print(1)
			done = True
			break
	if not done:
		print(0)


def main():
	t = int(input())
	for _ in range(t):
		(n, a, s, m) = (int(input()), list(map(int, input().split())), input(), [])
		for i in range(n - 1, -1, -1):
			ans = a[i]
			for j in m:
				ans = min(ans, ans ^ j)
			if s[i] == '0':
				if ans:
					m.append(ans)
			elif ans:
				print(1)
				break
		else:
			print(0)
main()


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	base = []
	for i in range(n - 1, -1, -1):
		v = a[i]
		for x in base:
			v = min(v, v ^ x)
		if v:
			if s[i] == '0':
				base.append(v)
			else:
				return 1
	return 0
t = int(input())
for _ in range(t):
	print(solve())


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	S = input().rstrip()
	win = set()
	win.add(0)
	for j in range(len(S) - 1, -1, -1):
		base = A[j]
		for v in win:
			base = min(base, base ^ v)
		if S[j] == '0':
			win.add(base)
		elif base:
			print('1')
			break
	else:
		print('0')


T = int(input())

def hakidasi(L):
	n = len(bin(max(L))) - 2
	(k, end) = (0, len(L))
	for i in range(n - 1, -1, -1):
		for j in range(k, end):
			if L[j] >> i & 1:
				(L[k], L[j]) = (L[j], L[k])
				break
		else:
			continue
		k += 1
		for j in range(end):
			if j == k - 1:
				continue
			if L[j] >> i & 1:
				L[j] ^= L[k - 1]
	return L

def judge(L, x):
	if L == []:
		return False
	n = len(bin(max(L))) - 2
	m = len(L)
	for i in range(m):
		a = len(bin(x))
		b = len(bin(L[i]))
		if a == b:
			x ^= L[i]
		elif a > b:
			return False
		if x == 0:
			return True
	return False

def main():
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	U = 60
	L = []
	for i in range(N - 1, -1, -1):
		if A[i] == 0:
			continue
		n = int(S[i])
		if n == 0:
			L.append(A[i])
			L = hakidasi(L)
			if L[-1] == 0:
				L.pop()
		else:
			m = judge(L, A[i])
			if m == False:
				return 1
	return 0
for i in range(T):
	print(main())


import sys
input = sys.stdin.readline

class BaseXor:

	def __init__(self):
		self.size = 0
		self.base = []

	def base_calculate(self, x, b):
		return min(x, x ^ b)

	def make_base(self, x):
		for b in self.base:
			x = self.base_calculate(x, b)
		return x

	def change_base(self, x):
		for i in range(self.size):
			self.base[i] = self.base_calculate(self.base[i], x)

	def judge_linearly_dependent(self, x, value=False):
		x = self.make_base(x)
		res = True if x else False
		res = (res, x) if value else res
		return res

	def add_base(self, x):
		(judge, x) = self.judge_linearly_dependent(x, value=True)
		if judge:
			self.change_base(x)
			self.base.append(x)
			self.size += 1
			return True
		return False

def solve(n, a, s):
	base = BaseXor()
	judge = False
	for i in range(n - 1, -1, -1):
		x = s[i]
		if x == '0':
			base.add_base(a[i])
		else:
			judge = base.judge_linearly_dependent(a[i])
			if judge:
				break
	res = 1 if judge else 0
	return res

def main():
	t = int(input())
	ans = [0] * t
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		s = input()
		res = solve(n, a, s)
		ans[i] = res
	print(*ans, sep='\n')
main()


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
sys.setrecursionlimit(2147483647)
INF = 10 ** 20

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
t = I()
for _ in range(t):
	n = I()
	A = LI()
	s = S()
	basis = []
	for i in range(n - 1, -1, -1):
		v = A[i]
		for b in basis:
			v = min(v, v ^ b)
		if v:
			if s[i] == '1':
				print(1)
				break
			basis += [v]
	else:
		print(0)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	S = input().strip()
	ignore = []
	win = True
	for i in range(N - 1, -1, -1):
		startLen = len(ignore)
		curr = A[i]
		for v in ignore:
			if curr ^ v < curr:
				curr = curr ^ v
		if curr != 0:
			ignore.append(curr)
			ignore.sort(reverse=True)
		endLen = len(ignore)
		if S[i] == '1' and startLen != endLen:
			win = False
			break
	if win:
		print(0)
	else:
		print(1)


import sys
readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
	INT_BITS = 64
	n = ni()
	a = nl()[::-1]
	s = ns()[::-1]
	lis = [0] * 64
	for i in range(n):
		if s[i] == '1':
			c = a[i]
			for x in lis[::-1]:
				if x == 0:
					continue
				if c & 1 << x.bit_length() - 1:
					c ^= x
			if c:
				print(1)
				return
		else:
			c = a[i]
			for x in lis[::-1]:
				if x == 0:
					continue
				if c & 1 << x.bit_length() - 1:
					c ^= x
			if c:
				lis[c.bit_length() - 1] = c
	print(0)
	return
T = ni()
for _ in range(T):
	solve()


T = int(input())

def check_base(bases, A):
	for (n, b) in bases:
		if A & 1 << n != 0:
			A ^= b
	if A == 0:
		return None
	n = 0
	d = 1
	while True:
		if A & d != 0:
			return (n, A)
		n += 1
		d <<= 1

def append_base(bases, A):
	pair = check_base(bases, A)
	if pair != None:
		bases.append(pair)

def check(N, A_list, S):
	bases = []
	for i in range(N - 1, -1, -1):
		A = A_list[i]
		if S[i] == '0':
			append_base(bases, A)
		elif check_base(bases, A):
			return False
	return True
for i in range(T):
	N = int(input())
	A_list = list(map(int, input().split()))
	S = input().strip()
	if check(N, A_list, S):
		print('0')
	else:
		print('1')


T = int(input())
for i in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	S = input()
	dp = []
	for j in reversed(range(n)):
		a = A[j]
		for x in dp:
			a = min(a, a ^ x)
		if a > 0:
			if S[j] == '0':
				dp.append(a)
			elif not A[j] in dp:
				print(1)
				break
	else:
		print(0)


I = input
n = int
for i in range(int(input())):
	I()
	t = []
	x = 0
	for (i, j) in zip(map(n, I().split()[::-1]), I()[::-1]):
		for k in t:
			i ^= k * (i ^ k < i)
		j = n(j)
		t.append(i * (j ^ 1))
		x |= (i > 0) & j
	print(x)


import sys

def main():

	def solve(S, A):
		X = []
		for (s, v) in zip(S[::-1], A[::-1]):
			for x in X:
				if v & (x & -x):
					v ^= x
			if v:
				if s == '0':
					X.append(v)
				else:
					return 1
		return 0
	T = int(input())
	for t in range(T):
		N = int(input())
		A = list(map(int, input().split()))
		S = input()
		print(solve(S, A))
	return
main()


def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = list(map(int, input().split()))
		S = input()
		L = max(A).bit_length()
		s = [0] * L
		ID = A.index(max(A))

		def check(x):
			for i in range(L - 1, -1, -1):
				if (x >> i) % 2:
					x ^= s[i]
			return x == 0

		def update(x):
			flag = False
			if x.bit_length() == 60:
				flag = True
			for i in range(L - 1, -1, -1):
				if (x >> i) % 2:
					x ^= s[i]
			id = x.bit_length() - 1
			if id >= 0:
				s[id] = x
		res = 0
		L2 = 0
		for i in range(N - 1, -1, -1):
			k = int(S[i])
			if k:
				if check(A[i]):
					continue
				else:
					res = 1
					break
			else:
				L2 = max(L2, A[i].bit_length())
				update(A[i])
		print(res)
main()


def base(a, f=False):
	k = 0
	for i in range(64):
		for ind in range(k, len(a)):
			j = a[ind]
			if j >> i & 1 == 1:
				break
		else:
			continue
		(a[ind], a[k]) = (a[k], a[ind])
		for (ind, j) in enumerate(a):
			if ind == k:
				continue
			if j >> i & 1 == 1:
				a[ind] ^= a[k]
		k += 1
		if k >= len(a):
			break
	return a[:k]
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	s = input()
	b = []
	for i in reversed(range(n)):
		if s[i] == '0':
			b = base(b + [a[i]])
		else:
			c = base(b[:] + [a[i]])
			if len(c) != len(b):
				print(1)
				break
	else:
		print(0)


def gauss_jordan(bs):
	rank = 0
	pivot_cols = []
	for col in reversed(range(61)):
		pivot = -1
		for (i, row) in enumerate(bs[rank:]):
			if row & 1 << col:
				pivot = rank + i
				break
		if pivot < 0:
			continue
		pivot_cols.append(col)
		(bs[pivot], bs[rank]) = (bs[rank], bs[pivot])
		for (i, row) in enumerate(bs):
			if i != rank and row & 1 << col:
				bs[i] ^= bs[rank]
		rank += 1
	return bs

def solve():
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	bs = []
	for (a, s) in zip(A[::-1], S[::-1]):
		x = a
		for b in bs:
			x = min(x, x ^ b)
		if x:
			if s == '0':
				bs.append(x)
				bs = gauss_jordan(bs)
			else:
				return 1
	return 0
T = int(input())
for _ in range(T):
	print(solve())


import sys
input = sys.stdin.readline
T = int(input())

def base(B):
	L = len(B)
	flag = 1
	while flag:
		B.sort(reverse=True)
		flag = 0
		for i in range(L):
			for j in range(i + 1, L):
				if B[i] ^ B[j] < B[i]:
					B[i] = B[i] ^ B[j]
					flag = 1
					break
			if flag:
				break
	return B

def rep(x):
	flag = 1
	while flag:
		flag = 0
		for b in B:
			if b ^ x < x:
				x = b ^ x
				flag = 1
				break
	return x
for tests in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = []
	S = input().strip()
	flag = 1
	for i in range(N - 1, -1, -1):
		if flag == 0:
			break
		if S[i] == '0':
			v = rep(A[i])
			if v == 0:
				continue
			B.append(v)
			B = base(B)
		elif rep(A[i]) != 0:
			print(1)
			flag = 0
			break
	if flag:
		print(0)


import sys
input = sys.stdin.readline

def matmul(a, b, mod):
	m = len(a)
	l = len(a[0])
	n = len(b[0])
	ret = [[0] * n for _ in range(m)]
	for i in range(m):
		for j in range(n):
			e = 0
			for k in range(l):
				e = (e + a[i][k] * b[k][j]) % 2
			ret[i][j] = e
	return ret

def calc(X, v, r):
	rr = 0
	for i in range(r, D):
		if v[i][0] == 1:
			rr = i
			break
	(v[rr], v[r]) = (v[r], v[rr])
	(X[rr], X[r]) = (X[r], X[rr])
	for i in range(D):
		if i == r or v[i][0] == 0:
			continue
		for c in range(D):
			X[i][c] = (X[i][c] + X[r][c]) % 2
T = int(input())
D = 64
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	S = input().rstrip()
	X = [[int(i == j) for j in range(D)] for i in range(D)]
	r = 0
	for i in range(N)[::-1]:
		v = [[A[i] >> j & 1] for j in range(D)]
		if S[i] == '0':
			v = matmul(X, v, 2)
			if any((v[j][0] == 1 for j in range(r, D))):
				calc(X, v, r)
				r += 1
		else:
			v = matmul(X, v, 2)
			if any((v[j][0] == 1 for j in range(r, D))):
				print(1)
				break
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	b = []
	ans = 0
	for i in range(n - 1, -1, -1):
		for j in b:
			a[i] = min(a[i], a[i] ^ j)
		if a[i] != 0:
			if s[i] == '0':
				b.append(a[i])
			else:
				ans = 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	(*a,) = map(int, input().split())
	s = input()
	b = []
	f = 0
	for (x, c) in zip(a[::-1], s[::-1]):
		for y in b:
			x = min(x, x ^ y)
		if x:
			if c == '1':
				f = 1
				break
			b.append(x)
	print(f)


def solve():
	dp = [[] for _ in range(n + 1)]
	dp[n].append(0)
	for i in range(n)[::-1]:
		dp[i] = dp[i + 1]
		x = a[i]
		for y in dp[i + 1]:
			x = min(x, x ^ y)
		if s[i] == '0':
			if x:
				dp[i].append(x)
		elif x:
			return 1
	return 0
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	print(solve())


T = int(input())

def standardize(x, base_set):
	base_list = sorted(base_set, reverse=True)
	for base in base_list:
		x = min(x, x ^ base)
	return x
for _ in range(T):
	N = int(input())
	alist = list(map(int, input().split()))
	slist = list(map(int, input()))
	base_set = set()
	for index in reversed(range(N)):
		norm_a = standardize(alist[index], base_set)
		if slist[index] == 0:
			base_set.add(norm_a)
		elif norm_a > 0:
			print(1)
			break
	else:
		print(0)


import sys
readline = sys.stdin.readline
T = int(readline())
Ans = [None] * T
for qu in range(T):
	N = int(readline())
	A = list(map(int, readline().split()))
	S = list(map(int, readline().strip()))
	if len(set(A)) == 1:
		Ans[qu] = S[-1]
		continue
	if S[-1] == 1:
		Ans[qu] = 1
		continue
	stack = [0] * 61
	for i in range(N - 1, -1, -1):
		a = A[i]
		for j in range(60, -1, -1):
			if a & 1 << j:
				a ^= stack[j]
		if S[i] == 0:
			if a:
				stack[a.bit_length() - 1] = a
			else:
				continue
		elif a:
			Ans[qu] = 1
			break
	else:
		Ans[qu] = 0
print('\n'.join(map(str, Ans)))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = [int(c) for c in input()]
	base = []
	for i in range(n - 1, -1, -1):
		v = a[i]
		for x in base:
			v = min(v, v ^ x)
		if v:
			if s[i] == 0:
				base.append(v)
			else:
				print(1)
				break
	else:
		print(0)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')

class BaseF2:

	def __init__(self, vs=None):
		self.base = []
		if vs is not None:
			for v in vs:
				tmp = v
				for u in self.base:
					tmp = min(tmp, tmp ^ u)
				if tmp > 0:
					self.base.append(tmp)

	def insert(self, v):
		for u in self.base:
			v = min(v, v ^ u)
		if v > 0:
			self.base.append(v)

	def check(self, v):
		for u in self.base:
			v = min(v, v ^ u)
		return v == 0

	def clear(self):
		self.base = []
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	b0 = BaseF2()
	b1 = BaseF2()
	done = False
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			b1.insert(a[i])
		else:
			b0.insert(a[i])
		for item in b1.base:
			if not b0.check(item):
				print(1)
				done = True
				break
		if done:
			break
	else:
		print(0)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
t = int(readline())

def get_base(x, basis):
	for b in basis:
		x = min(x, x ^ b)
	return x
for _ in range(t):
	n = int(readline())
	a = list(map(int, readline().split()))
	s = readline().strip()
	basis = []
	for (si, ai) in zip(s[::-1], a[::-1]):
		x = get_base(ai, basis)
		if (si == '0') & (x > 0):
			basis.append(x)
		elif (si == '1') & (x > 0):
			print(1)
			break
	else:
		print(0)


T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	A = [int(_) for _ in input().split()]
	S = input()
	dp = set([0])
	for (a, s) in zip(A[::-1], S[::-1]):
		for b in dp:
			a = min(a, a ^ b)
		if s == '1':
			if a:
				dp = set()
				break
		else:
			dp2 = set([a])
			for b in dp:
				dp2.add(min(b, a ^ b))
			dp = dp2
	ans += [0 if 0 in dp else 1]
print(*ans, sep='\n')


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
sys.setrecursionlimit(2147483647)
INF = 10 ** 20

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

def least_bit_set(x):
	return x & -x

def delete_zeros_from(values, start):
	i = start
	for j in range(start, len(values)):
		if values[j] != 0:
			values[i] = values[j]
			i += 1
	del values[i:]

def eliminate(values):
	values = list(values)
	i = 0
	while True:
		delete_zeros_from(values, i)
		if i >= len(values):
			return values
		j = i
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) < least_bit_set(values[j]):
				j = k
		(values[i], values[j]) = (values[j], values[i])
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) == least_bit_set(values[i]):
				values[k] ^= values[i]
		i += 1

def in_span(x, eliminated_values):
	for y in eliminated_values:
		if least_bit_set(y) & x != 0:
			x ^= y
	return x == 0
t = I()
for _ in range(t):
	n = I()
	A = LI()
	s = S()
	flg = 0
	values = []
	for j in range(n - 1, -1, -1):
		if int(s[j]) == 0:
			values += [A[j]]
			values = eliminate(values)
		elif not in_span(A[j], values):
			print(1)
			break
	else:
		print(0)


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])

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 c == '0':
			sZ |= {v}
		elif v not in sZ:
			sZ = set({})
			break
	res = 1
	if sZ:
		res = 0
	print(res)

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

def ran():
	N = 200
	vRan = [random.randint(1, 10) for _ in '*' * N]
	S = ''.join((str(random.randint(0, 1)) for _ in '*' * N))
	print(vRan, S)
	sol(N=0, vA=vRan, S=S)
	exit(0)
main()


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	for t in range(int(input())):
		N = int(input())
		A = list(map(int, input().split()))
		S = input().rstrip('\n')
		A.reverse()
		S = S[::-1]
		A0 = [0] * 60
		A1 = [0] * 60
		zero = 0
		one = 0
		for (i, a) in enumerate(A):
			if S[i] == '0':
				for j in range(60):
					A0[j] ^= (a >> j & 1) << zero
				zero += 1
			else:
				for j in range(60):
					A1[j] ^= (a >> j & 1) << one
				one += 1
		B = [0] * 60
		for i in range(60):
			B[i] = A0[i] + (A1[i] << zero)
		rnk = 0
		for i in range(zero):
			for j in range(rnk, 60):
				if B[j] >> i & 1:
					(B[j], B[rnk]) = (B[rnk], B[j])
					b = B[rnk]
					for jj in range(60):
						if jj == rnk:
							continue
						if B[jj] >> i & 1:
							B[jj] ^= b
					rnk += 1
					break
		cnt0 = 0
		cnt1 = zero
		r = -1
		win = 0
		for s in S:
			if s == '0':
				if r + 1 >= len(B):
					break
				if B[r + 1] >> cnt0 & 1:
					r += 1
				cnt0 += 1
			else:
				rr = -1
				for j in range(60):
					if B[j] >> cnt1 & 1:
						rr = j
				if rr > r:
					win = 1
					break
				cnt1 += 1
		print(win)
main()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 8)
INF = float('inf')

def main():
	T = int(input())
	for t in range(T):
		N = int(input())
		A = list(map(int, input().split()))
		S = input()
		lose = False
		X = []
		for i in reversed(range(N)):
			v = A[i]
			for x in X:
				if v & (x & -x):
					v ^= x
			if v != 0:
				if S[i] == '0':
					X.append(v)
				else:
					lose = True
					break
		if lose == True:
			print(1)
		else:
			print(0)
	return
main()


def main():

	def sweep(arr):
		col = max(arr).bit_length()
		row = len(arr)
		rank = 0
		for c in range(col - 1, -1, -1):
			piv = -1
			for r in range(rank, row):
				if arr[r] >> c & 1:
					piv = r
			if piv == -1:
				continue
			(arr[piv], arr[rank]) = (arr[rank], arr[piv])
			for r in range(row):
				if r == rank:
					continue
				if arr[r] >> c & 1:
					arr[r] ^= arr[rank]
			rank += 1
		return sorted(arr[:rank], reverse=True)

	def solve():
		N = int(input())
		A = list(map(int, input().split()))[::-1]
		S = input()[::-1]
		B0 = []
		for (a, s) in zip(A, S):
			if s == '1':
				for b0 in B0:
					if a >> b0.bit_length() - 1 & 1:
						a ^= b0
				if a:
					return 1
			else:
				B0 = sweep(B0 + [a])
		return 0
	for _ in [0] * int(input()):
		print(solve())
main()


def collapse(A):
	R = []
	a = max(A)
	n = a.bit_length()
	B = [set() for _ in range(n)]
	for a in A:
		B[a.bit_length()].add(a)
	for i in reversed(range(n)):
		if not B[i]:
			continue
		b = B[i].pop()
		R.append(b)
		for k in B[i]:
			k ^= b
			B[k.bit_length()].add(k)
	return R

def solve(N, A, S):
	B = [0] * 64
	for (a, s) in zip(reversed(A), reversed(S)):
		if s == '1':
			n = a.bit_length() - 1
			while a != 0:
				if B[n] == 0:
					return 1
				a ^= B[n]
				n = a.bit_length() - 1
		else:
			n = a.bit_length() - 1
			while a != 0 and B[n] != 0:
				a ^= B[n]
				n = a.bit_length() - 1
			if a == 0:
				continue
			B[n] = a
	return 0

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = list(map(int, input().split()))
		S = input()
		print(solve(N, A, S))
main()


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	base = []
	for i in range(1, N + 1):
		temp = A[-i]
		for x in base:
			temp = min(temp, temp ^ x)
		if temp != 0:
			if S[-i] == '1':
				print('1')
				break
			else:
				base.append(temp)
	else:
		print('0')


from collections import Counter
import math
import sys
from bisect import bisect, bisect_left, bisect_right

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def mod():
	return 10 ** 9 + 7
for _ in range(INT()):
	n = INT()
	arr = LIST()
	s = input()
	check = []
	flag = 0
	for i in range(n - 1, -1, -1):
		x = arr[i]
		for j in range(len(check)):
			x = min(x, x ^ check[j])
		if x == 0:
			continue
		if s[i] == '0':
			check.append(x)
		else:
			print(1)
			flag = 1
			break
	if flag == 0:
		print(0)


def solve(N, A, S):
	if int(S[-1]) == 1:
		return 1
	B = [None] * max(A).bit_length()
	for i in reversed(range(N)):
		a = A[i]
		s = int(S[i])
		if s == 0:
			while a:
				l = a.bit_length() - 1
				if B[l] == None:
					B[l] = a
					break
				a ^= B[l]
		else:
			while a:
				l = a.bit_length() - 1
				if B[l] == None:
					return 1
				a ^= B[l]
	return 0
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	print(solve(N, A, S))


def solve(n, a_list, s):
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			if a_list[i] == 0:
				continue
			r = 2 ** (a_list[i].bit_length() - 1)
			for j in range(i):
				if a_list[j] & r > 0:
					a_list[j] = a_list[i] ^ a_list[j]
		elif a_list[i] > 0:
			return 1
	return 0

def main():
	t = int(input())
	res_list = []
	for _ in range(t):
		n = int(input())
		a_list = list(map(int, input().split()))
		s = input()
		res = solve(n, a_list, s)
		res_list.append(res)
	for res in res_list:
		print(res)

def test():
	assert solve(2, [1, 2], '10') == 1
	assert solve(2, [1, 1], '10') == 0
	assert solve(6, [2, 3, 4, 5, 6, 7], '111000') == 0
test()
main()


def solve(*args: str) -> str:
	t = int(args[0])
	ret = []
	for i in range(1, 3 * t + 1, 3):
		n = int(args[i])
		A = tuple(map(int, args[i + 1].split()))
		S = tuple(map(int, tuple(args[i + 2])))
		ans = False
		dp = [0] * (max(A).bit_length() + 1)
		for (a, s) in reversed(tuple(zip(A, S))):
			m = a.bit_length()
			if s == 0:
				while 0 < a and 0 < dp[m]:
					a ^= dp[m]
					m = a.bit_length()
				if 0 < a:
					dp[m] = a
			elif s == 1:
				while 0 < a:
					if 0 < dp[m]:
						a ^= dp[m]
						m = a.bit_length()
					else:
						ans = True
						break
		ret.append(1 * ans)
	return '\n'.join(map(str, ret))
print(solve(*open(0).read().splitlines()))


import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop
n1 = lambda : int(sys.stdin.readline().strip())
nn = lambda : list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda : float(sys.stdin.readline().strip())
fn = lambda : list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda : sys.stdin.readline().strip()
sn = lambda : list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0):
	return [d] * n

def array2(n, m, d=0):
	return [[d] * m for x in range(n)]

def array3(n, m, l, d=0):
	return [[[d] * l for y in xrange(m)] for x in xrange(n)]

def ldec(A, d=1):
	return map(lambda x: x - d, A)

def solve(N, A, S):
	dp = [0]
	for i in range(N - 1, -1, -1):
		ai = A[i]
		if S[i] == '0':
			for d in dp:
				if ai > ai ^ d:
					ai ^= d
			if ai:
				dp.append(ai)
		if S[i] == '1':
			for b in dp:
				if ai > ai ^ b:
					ai ^= b
			if ai:
				print('1')
				return
	print('0')
T = n1()
for _ in range(T):
	N = n1()
	A = nn()
	S = s1()
	solve(N, A, S)


import sys
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
T = ir()
for _ in range(T):
	N = ir()
	A = lr()
	S = sr()
	zero_cards = []
	for (a, person) in zip(A[::-1], S[::-1]):
		for z in zero_cards:
			a = min(a, a ^ z)
		if a:
			if person == '1':
				print(1)
				break
			zero_cards.append(a)
	else:
		print(0)


from itertools import groupby, chain
from operator import itemgetter

def sweep(l):
	result = []
	s = set(l)
	while s:
		a = max(s)
		b = 1 << a.bit_length() - 1
		s = {t ^ a if t >= b else t for t in s}
		s.discard(0)
		result.append([a, b])
	return result
t = int(input())
buf = []
for _ in range(t):
	n = int(input())
	aaa = list(map(int, input().split()))
	s = input()
	if s[-1] == '1':
		buf.append(1)
		continue
	grp = [list(map(itemgetter(1), itr)) for (c, itr) in groupby(zip(s, aaa), key=itemgetter(0))]
	if s[0] == '0':
		grp = grp[1:]
	grp1 = grp[0::2]
	grp0 = grp[1::2]
	erasable = [False] * sum((len(g) for g in grp1))
	for i in range(len(grp1)):
		l1 = list(chain(*grp1[:i + 1]))
		l0 = list(chain(*grp0[i:]))
		s0 = sweep(l0)
		for (a, b) in s0:
			for i in range(len(l1)):
				if l1[i] & b:
					l1[i] ^= a
		for (j, c) in enumerate(l1):
			if c == 0:
				erasable[j] = True
	if all(erasable):
		buf.append(0)
	else:
		buf.append(1)
print('\n'.join(map(str, buf)))


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
t = I()
for _ in range(t):
	n = I()
	a = LI()
	s = input()
	t = []
	for (i, Ai) in enumerate(a[::-1]):
		for Ti in t:
			if Ai ^ Ti < Ai:
				Ai ^= Ti
		if Ai != 0 and s[n - i - 1] == '0':
			t.append(Ai)
		elif Ai != 0 and s[n - i - 1] == '1':
			print(1)
			break
	else:
		print(0)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = list(input())
	l = []
	f = False
	for i in range(n)[::-1]:
		for j in l:
			a[i] = min(a[i], a[i] ^ j)
		if a[i]:
			if s[i] == '0':
				l.append(a[i])
			else:
				print(1)
				f = True
				break
	if f:
		continue
	print(0)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	ans = 0
	B = []
	for i in range(N)[::-1]:
		a = A[i]
		for b in B:
			a = min(a, a ^ b)
		if a:
			if S[i] == '1':
				ans = 1
				break
			B.append(a)
	print(ans)


m = (10 ** 18).bit_length()

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	s = list(map(int, input()))
	base = [0] * m
	for i in reversed(range(n)):
		for j in reversed(range(m)):
			if 1 << j & a[i]:
				if base[j] == 0:
					if s[i]:
						print('1')
						return
					else:
						base[j] = a[i]
					break
				a[i] ^= base[j]
	print('0')
t = int(input())
for i in range(t):
	solve()


def solve():
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	ans = '0'
	for i in range(N):
		if S[i] == '1':
			l = []
			for j in range(i + 1, N):
				if S[j] == '0':
					l.append(A[j])
			for k in range(len(l)):
				l.sort()
				for j in range(len(l) - 1):
					if l[j + 1] ^ l[j] < l[j + 1]:
						(l[j + 1], l[j]) = (l[j], l[j + 1] ^ l[j])
			s = A[i]
			for j in range(len(l) - 1, -1, -1):
				if s ^ l[j] < s:
					s ^= l[j]
			if s != 0:
				ans = '1'
	print(ans)

def main():
	T = int(input())
	for t in range(T):
		solve()
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	basis = []
	ans = 0
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			for b in basis:
				a[i] = min(a[i], a[i] ^ b)
			if a[i]:
				basis.append(a[i])
		else:
			for b in basis:
				a[i] = min(a[i], a[i] ^ b)
			if a[i]:
				ans = 1
				break
	print(ans)


import sys
input = sys.stdin.readline

def standard_form(A):
	C = A[:]
	L = 60
	E = []
	ids = []
	for i in range(L):
		e = j0 = None
		mask = (1 << i) - 1
		for (j, a) in enumerate(C):
			if a >> i & 1 and a & mask == 0:
				e = a
				j0 = j
				break
		else:
			continue
		ids.append(j0)
		for (j, a) in enumerate(C):
			if j0 == j:
				continue
			if a >> i & 1:
				C[j] ^= e
	return [C[e] for e in ids]
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	A = []
	B = []
	task = set([0])
	now = s[n - 1]
	if now == '1':
		print(1)
		continue
	q = []
	win = '0'
	for i in range(n - 1, -1, -1):
		if now == '0':
			if s[i] == '0':
				q.append(a[i])
			else:
				q = standard_form(q)
				task = task | set(q)
				task = set(standard_form(list(task)))
				q = [a[i]]
				now = '1'
		elif s[i] == '1':
			q.append(a[i])
		else:
			q = standard_form(q)
			q = set(q) | task
			q = set(standard_form(list(q)))
			if task != task | q:
				win = '1'
				break
			q = [a[i]]
			now = '0'
	if now == '1':
		q = standard_form(list(q))
		q = set(q) | task
		q = standard_form(list(q))
		q = set(q)
		if task != task | q:
			win = '1'
	print(win)


def is_included(base, X):
	base.sort(reverse=True)
	V = X
	for x in base:
		V = min(V, V ^ x)
	return V

def solve():
	N = int(input())
	a = list(map(int, input().split()))[::-1]
	player = input()[::-1]
	basement = [0]
	for i in range(N):
		v = a[i]
		K = is_included(basement, v)
		if player[i] == '0':
			if K == 0:
				pass
			else:
				basement.append(K)
		elif K == 0:
			pass
		else:
			return 1
	return 0

def main():
	T = int(input())
	for i in range(T):
		A = solve()
		print(A)
	return
main()


t = int(input())
scale = 64
double = [2 ** d for d in range(scale)]
double.reverse()
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	base = [0 for _ in range(scale)]
	for i in range(n)[::-1]:
		now = a[i]
		for d in range(scale):
			if now & double[d]:
				if base[d]:
					now ^= base[d]
				else:
					base[d] = now
					break
		else:
			continue
		if s[i] == '1':
			print(1)
			break
	else:
		print(0)


from bisect import insort
t = int(input())
buf = []
for _ in range(t):
	n = int(input())
	aaa = list(map(int, input().split()))
	s = input()
	is_ok = 0
	can = []
	for i in range(n - 1, -1, -1):
		a = aaa[i]
		if s[i] == '0':
			for (b, c) in can[::-1]:
				if a & b:
					a ^= c
			if a:
				b = 1 << a.bit_length() - 1
				insort(can, (b, a))
		else:
			for (b, c) in can[::-1]:
				if a & b:
					a ^= c
			if a:
				is_ok = 1
				break
	buf.append(is_ok)
print('\n'.join(map(str, buf)))


for _ in range(int(input())):
	input()
	(*a,) = map(int, input().split())
	s = input()
	b = []
	ans = 0
	for (x, p) in zip(a[::-1], s[::-1]):
		for y in b:
			x = min(x, x ^ y)
		if x:
			if p == '1':
				ans = 1
				break
			b.append(x)
	print(ans)


class VectorSpace:

	def __init__(self, k):
		self.k = k
		self.E = [0] * k

	def chk(self, n):
		for i in range(self.k)[::-1]:
			n = min(n, n ^ self.E[i])
		return 1 if n == 0 else 0

	def add(self, n):
		for i in range(self.k)[::-1]:
			n = min(n, n ^ self.E[i])
		if n:
			self.E[n.bit_length() - 1] = n
		return 1 if n == 0 else 0

	def dimension(self):
		return len(self.E)
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()]
	vs = VectorSpace(60)
	for i in range(N)[::-1]:
		a = vs.add(A[i])
		if S[i] and a == 0:
			print(1)
			break
	else:
		print(0)


def kosu(kitei, aaa, tuika):
	global now_ret
	ret = 0
	n = len(kitei)
	ret2 = 0
	kitei.append(aaa)
	n += 1
	for i in range(n):
		if kitei[i]:
			ret2 += 1
			x = 0
			while 2 ** (x + 1) <= kitei[i]:
				x += 1
			for y in range(i + 1, n, 1):
				if kitei[y] & 2 ** x:
					kitei[y] ^= kitei[i]
	if now_ret == ret2:
		return 1
	else:
		if tuika == 1:
			now_ret += 1
		return 0

def solve(n, alist, s):
	kitei = [0]
	answer = 0
	for i in range(n):
		teban = s[n - i - 1]
		now = alist[n - i - 1]
		if teban == '0':
			if kosu(kitei, now, 1) > 0:
				pass
			else:
				kitei.append(now)
		elif kosu(kitei, now, 0) > 0:
			pass
		else:
			answer = 1
	return answer
t = int(input())
for i in range(t):
	now_ret = 0
	n = int(input())
	alist = list(map(int, input().split()))
	s = input()
	print(solve(n, alist, s))


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	l = []
	ans = 0
	for (a, s) in zip(A[::-1], S[::-1]):
		for b in l:
			a = min(a, a ^ b)
		if a != 0:
			if s == '1':
				ans = 1
			l.append(a)
	print(ans)


T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))[::-1]
	S = input()
	S = [1 if c == '1' else 0 for c in S][::-1]
	l = []
	r = 0
	for (i, a) in enumerate(A):
		if S[i]:
			for e in sorted(l)[::-1]:
				b = pow(2, e.bit_length() - 1)
				if a & b:
					a ^= e
			if a:
				r = 1
		else:
			for e in l:
				if a > e ^ a:
					a ^= e
			if a:
				l.append(a)
	print(r)


def solve(N, A, S):
	dp = []
	for i in reversed(range(N)):
		x = A[i]
		for v in dp:
			x = min(x, v ^ x)
		if x > 0:
			if S[i] == '0':
				dp.append(x)
			else:
				return 1
	return 0

def main():
	T = int(input())
	ans = [None] * T
	for i in range(T):
		N = int(input())
		A = list(map(int, input().split()))
		S = input()
		ans[i] = solve(N, A, S)
	for v in ans:
		print(v)
main()


for i in range(int(input())):
	input()
	t = []
	for (i, j) in zip(map(int, input().split()[::-1]), input()[::-1]):
		for k in t:
			i ^= k * (i ^ k < i)
		if i and j == '0':
			t.append(i)
		if i and j == '1':
			print(1)
			break
	else:
		print(0)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	b = []
	for i in range(n)[::-1]:
		for e in b:
			a[i] = min(a[i], a[i] ^ e)
		if a[i]:
			if s[i] == '0':
				b += [a[i]]
			else:
				print(1)
				break
	else:
		print(0)


sc = iter(open(0).read().split())
ni = lambda : int(next(sc))
ns = lambda : next(sc)
T = ni()
for _ in range(T):
	N = ni()
	A = [ni() for _ in range(N)]
	S = ns()
	B = []
	ans = 0
	for (a, s) in zip(reversed(A), reversed(S)):
		for b in B:
			a = min(a, a ^ b)
		if a:
			if s == '1':
				ans = 1
				break
			else:
				B.append(a)
	print(ans)


import sys
input = sys.stdin.readline
Q = int(input())
Query = []
for _ in range(Q):
	N = int(input())
	A = list(map(int, input().split()))
	S = input().rstrip()
	Query.append((N, A, S))

def solve(N, A, S):
	Base = []
	for i in reversed(range(N)):
		s = S[i]
		a = A[i]
		if s == '0':
			for b in Base:
				a = min(a, a ^ b)
			if a:
				Base.append(a)
		else:
			for b in Base:
				a = min(a, a ^ b)
			if a:
				return False
	return True
for (N, A, S) in Query:
	print(0 if solve(N, A, S) else 1)


def msb(x):
	cnt = 0
	while x:
		x >>= 1
		cnt += 1
	return cnt

def solve(n, a, s):
	dp = [[] for _ in range(n + 1)]
	for i in reversed(range(n)):
		if s[i] == '0':
			x = a[i]
			dp[i] = dp[i + 1].copy()
			dp[i].sort(reverse=True)
			for j in range(len(dp[i])):
				x = min(x, x ^ dp[i][j])
			if x != 0:
				dp[i].append(x)
		else:
			x = a[i]
			dp[i + 1].sort(reverse=True)
			for j in range(len(dp[i + 1])):
				x = min(x, x ^ dp[i + 1][j])
			if x == 0:
				dp[i] = dp[i + 1].copy()
			else:
				return '1'
	if len(dp[0]) != 0:
		return '0'
	else:
		return '1'
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	ans = solve(n, a, s)
	print(ans)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	basis = []
	for i in range(n - 1, -1, -1):
		for e in basis:
			a[i] = min(a[i], a[i] ^ e)
		if a[i]:
			if s[i] == '0':
				basis.append(a[i])
			else:
				print(1)
				return
	print(0)
t = int(input())
for _ in range(t):
	solve()


import sys
input = sys.stdin.readline

def judge(mat, x, pivot):
	b = x.bit_length()
	cnt = 0
	for i in range(b)[::-1]:
		if x & 1 << i:
			if i not in pivot:
				return False
			for j in range(cnt, len(mat)):
				if mat[j] & 1 << i:
					x ^= mat[j]
					cnt = j + 1
					break
	if x == 0:
		return True
	else:
		return False

def add(mat, x, pivot):
	b = x.bit_length()
	cnt = 0
	for i in range(b)[::-1]:
		if x & 1 << i:
			if i in pivot:
				for j in range(cnt, len(mat)):
					if mat[j] & 1 << i:
						x ^= mat[j]
						cnt = j + 1
						break
			else:
				pivot.add(i)
				for j in range(len(mat)):
					if mat[j] < x:
						mat.insert(j, x)
						for k in range(i)[::-1]:
							if mat[j] & 1 << k and k in pivot:
								for l in range(j + 1, len(mat)):
									if mat[l] & 1 << k:
										mat[j] ^= mat[l]
						x = mat[j]
						break
				else:
					mat.append(x)
				for j in range(len(mat)):
					if mat[j] > x and mat[j] & 1 << i:
						mat[j] ^= x
				break
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input().rstrip()
	pivot = set()
	mat = []
	for i in range(n)[::-1]:
		x = a[i]
		if s[i] == '0':
			if judge(mat, x, pivot):
				continue
			else:
				add(mat, x, pivot)
		elif judge(mat, x, pivot):
			continue
		else:
			print(1)
			break
	else:
		print(0)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(item) for item in input().split()]
	s = input().rstrip()
	if s[-1] == '1':
		print(1)
		continue
	group = []
	prev = '-1'
	for (ch, num) in zip(s, a):
		if prev != ch:
			group.append([])
		group[-1].append(num)
		prev = ch
	group.reverse()
	tools = []
	ok = True
	for (itr, g) in enumerate(group):
		if itr % 2 == 0:
			for item in g:
				tools.append(item)
		else:
			tl = tools[:]
			index = 0
			for i in range(64, -1, -1):
				flag = 0
				for j in range(index, len(tl)):
					if tl[j] & 1 << i:
						flag = 1
						(tl[index], tl[j]) = (tl[j], tl[index])
						break
				for j in range(index + 1, len(tl)):
					if tl[j] & 1 << i:
						tl[j] ^= tl[index]
				if flag == 1:
					index += 1
			for item in g:
				current = 0
				for val in tl:
					index = len(bin(val)) - 3
					if item >> index != current >> index:
						current ^= val
				if current != item:
					ok = False
	if ok:
		print(0)
	else:
		print(1)


def gauss_jordan(A):
	m = len(A)
	n = len(A[0])
	rank = 0
	for col in range(n):
		pivot = -1
		for row in range(rank, m):
			if A[row][col] != 0:
				pivot = row
				break
		if pivot == -1:
			continue
		(A[pivot], A[rank]) = (A[rank], A[pivot])
		for row in range(m):
			if row != rank and A[row][col] != 0:
				for col2 in range(n):
					A[row][col2] ^= A[rank][col2]
		rank += 1
	if rank == len(A):
		return True
	else:
		return False

def make_vector(val):
	ret = []
	for i in range(60, -1, -1):
		if val & 1 << i:
			ret.append(1)
		else:
			ret.append(0)
	return ret
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = input()
	if s[-1] == '1':
		print(1)
		continue
	A = [make_vector(arr[-1])]
	for i in range(n - 2, -1, -1):
		vector = make_vector(arr[i])
		if gauss_jordan(A + [vector]):
			if s[i] == '1':
				print(1)
				break
			if s[i] == '0':
				A.append(vector)
	else:
		print(0)