Problem:
 Score : 400 points    Problem Statement 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.        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 1 replaces x with 0 \oplus 1=1 , we surely have x \neq 0 at the end of the game, regardless of the choice of Person 0 .  In the second test case, regardless of the choice of Person 1 , Person 0 can make x=0 with a suitable choice.

Solution (Python):
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")
    
if __name__ == "__main__":
    main()

Solution (Python):
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 add_base(self, x):
        x = self.make_base(x)
        if x == 0:
            return False
        self.change_base(x)
        self.base.append(x)
        self.size += 1
        return True
    
    def judge_linearly_dependent(self, x):
        for b in self.base:
            x = self.base_calculate(x, b)
        res = True if x else False
        return res

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")
    
if __name__ == "__main__":
    main()

Solution (Python):
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 add_base(self, x):
        x = self.make_base(x)
        if x == 0:
            return False
        self.change_base(x)
        self.base.append(x)
        self.base.sort()
        self.size += 1
        return True
    
    def judge_linearly_dependent(self, x):
        for b in self.base:
            x = self.base_calculate(x, b)
        res = True if x else False
        return res

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")
    
if __name__ == "__main__":
    main()

Solution (Python):
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()

Solution (Python):
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)

if __name__ == '__main__':
    main()

Solution (Python):
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]))

Solution (Python):
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)

Solution (Python):

"""

https://atcoder.jp/contests/agc045/tasks/agc045_a

A[i]が正なので、最後が人1ならば絶対1がかつ

あとは最後が0の場合を考える
→人0が作れない数字を作れればおk

Xorは戻る演算であることを考慮

◎仮説
1の持ってる数それぞれについて、0がそれ以降の数を使って作れるなら0の勝ち。
そうでないなら1の勝ち

まず、1が持っているある数に関して、それ以降で打ち消せることが必要十分条件であることの証明
それ以前に0が対策しておいたとする。1が使わなかった場合、0はそれ以降で対策を打ち消さなくてはいけない。
すなわち、1が行動した後にできる行動 = 対策のためにできる行動
なので、必要十分である

1が持つ複数の数字に関して、それぞれ後ろで打ち消せればいいことの証明
S,Tという2つの数があり、それぞれ後ろで打ち消せるとする。
SとTを打ち消すための集合を全部選ぶと、そのXorはS^Tとなるので打ち消せる
よって示された

あとは、O(N**2)で求められればおk
追加するときに、まだ分離できていない桁かつ1の桁を見つけて分離すればおk

2**60なので

"""

from sys import stdin

TT = int(stdin.readline())

for loop in range(TT):

    N = int(stdin.readline())
    A = list(map(int,stdin.readline().split()))
    S = stdin.readline()
    S = S[:-1]

    zerolis = []
    root = [None] * 60

    for i in range(N-1,-1,-1):

        
        if S[i] == "0":

            
            now = A[i]
            for j in range(60):
                if root[j] != None and now & (2**j) > 0:
                    now ^= zerolis[root[j]]

            
            for j in range(60):
                if root[j] == None and now & (2**j) > 0:
                    
                    for k in range(len(zerolis)):
                        if zerolis[k] & (2**j) > 0:
                            zerolis[k] ^= now

                    root[j] = len(zerolis)
                    zerolis.append(now)
                    break

        else: 

            now = A[i]
            for j in range(60):
                if root[j] != None and now & (2**j) > 0:
                    now ^= zerolis[root[j]]

            if now != 0:
                print (1)
                break
    else:
        print (0)

Solution (Python):



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)
        else:
            if K == 0:
                pass
            else:
                return 1

    return 0


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


if __name__ == "__main__":
    main()

Solution (Python):



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)
        else:
            if K == 0:
                pass
            else:
                return 1

    return 0


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


if __name__ == "__main__":
    main()

Solution (Python):
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()


if __name__ == '__main__':
    main()

Solution (Python):
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)
	
if __name__ == "__main__":
	
	main()

Solution (Python):
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))

Solution (Python):
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):
        """vs: list of vecotr in F2
        """
        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)

Solution (Python):
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')

Solution (Python):
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)

Solution (Python):
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)

if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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())

Solution (Python):
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

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

if __name__ == '__main__':
  main()

Solution (Python):
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())

Solution (Python):
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

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

if __name__ == '__main__':
  main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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 != 0:
                print("1")
                return

    print("0")

T = n1()
for _ in range(T):
    N = n1()
    A = nn()
    S = s1()
    solve(N, A, S)

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))






def F2_update_basis(A,x):
    for a in A:
        x = min(x,x^a)
    if x:
        A.append(x)
    return A

T = I()
ans = []
for i in range(T):
    N = I()
    A = LI()
    S = list(input())
    d = []
    flag = False
    for j in range(N)[::-1]:
        if S[j] == '0':
            d = F2_update_basis(d,A[j])
        else:
            num = len(d)
            d = F2_update_basis(d,A[j])
            if len(d) != num:
                flag = True
                ans.append(1)
                break
    if not flag:
        ans.append(0)

for a in ans:
    print(a)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))






def F2_row_reduction(A):
    n = len(A)
    g = A[:]
    rank = 0
    max_digit = len(format(max(A),'b'))
    for col in range(max_digit)[::-1]:
        pivot = -1
        for row in range(rank,n):
            if g[row]>>col & 1:
                pivot = row
                break
        if pivot == -1: 
            continue
        g[pivot],g[rank] = g[rank],g[pivot]
        for row in range(rank+1,n):
            if g[row]>>col & 1:
                g[row] ^= g[rank]
        rank += 1
    return g

T = I()
ans = []
for i in range(T):
    N = I()
    A = LI()
    S = list(input())
    d = []
    flag = False
    for j in range(N)[::-1]:
        rank = 0
        if S[j] == '0':
            d.append(A[j])
            d = F2_row_reduction(d)
            if d[-1] == 0:
                d.pop()
            else:
                rank += 1
        else:
            d.append(A[j])
            d = F2_row_reduction(d)
            if d[-1] == 0:
                d.pop()
            else:
                flag = True
                ans.append(1)
                break
    if not flag:
        ans.append(0)

for a in ans:
    print(a)

Solution (Python):


def solve():
    base = []
    for a, s in zip(A[::-1], map(int, S[::-1])):
        x = a
        for b in base:
            x = min(x, x ^ b)
        if x:
            if s ^ 1:
                base.append(x)
            else:
                return 1
    return 0


t = int(input())
for _ in range(t):
    n = int(input())
    A = list(map(int, input().split()))
    S = input()
    print(solve())

Solution (Python):





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

Solution (Python):
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())