Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
n, ww = map(int, input().split())
dp = np.zeros([n, ww+1], dtype='int64')
w, v = map(int, input().split())
dp[0] = np.array([v if i >= w else 0 for i in range(ww+1)])
for i in range(1, n):
  w, v = map(int, input().split())
  for j in range(1,ww+1):
    if j+w <= ww:
      dp[i][j+w] = np.maximum(dp[i-1][j+w], dp[i-1][j]+v)
    dp[i][j] = np.maximum(dp[i-1][j],dp[i][j])

print(dp[-1][-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, W = map(int, input().split())
dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]
print(knapsack(N, W))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N = int(input())

As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
Cs = list(map(int, input().split()))

As.sort()
Bs.sort()
Cs.sort()

ans = 0
for a in As:
    for b in Bs:
        if a >= b:
            continue
        for c in Cs:
            if b >= c:
                continue
            #print(a,b,c)
            ans += 1

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
N = int(input())

As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
Cs = list(map(int, input().split()))

As.sort()
Bs.sort()
Cs.sort()

ans = 0
# for a in As:
#     for b in Bs:
#         if a >= b:
#             continue
#         for c in Cs:
#             if b >= c:
#                 continue
#             #print(a,b,c)
#             ans += 1
#
# print(ans)

Bcnt = [0 for i in range(N)]
i = 0
for b in Bs:
    cnt = N - bisect.bisect_right(Cs, b)
    # print(b, cnt)
    Bcnt[i] = cnt
    i += 1

Bsum = [0 for i in range(N)]
Bsum[N-1] = Bcnt[N-1]
for i in range(N-2, -1, -1):
    Bsum[i] = Bsum[i+1] + Bcnt[i]
    # print(i, Bsum)

for a in As:
    cnt = bisect.bisect_right(Bs, a)
    if cnt == N:
        ans += 0
    else:
        ans += Bsum[cnt]

# print(Bcnt)
# print(Bsum)
print(ans)
### BUGGY CODE ###

from itertools import permutations


N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]
cost = [[0] * 3 for _ in range(C)]

for i in range(N):
    for j in range(N):
        for k in range(C):
            cost[k][(i + j) % 3] += D[c[i][j] - 1][k]


ans = min(
    sum(cost[c][i] for i, c in enumerate(colors))
    for colors in permutations(range(C), 3)
)
print(ans)


### FIXED CODE ###

from itertools import permutations


N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]
cost = [[0] * 3 for _ in range(C)]

for i in range(N):
    for j in range(N):
        for k in range(C):
            cost[k][(i + j) % 3] += D[c[i][j] - 1][k]

ans = min(
    sum(cost[c][i] for i, c in enumerate(colors))
    for colors in permutations(range(C), 3)
)
print(ans)
### BUGGY CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def warshall_floyd(d,n):
    for i in range(n):
        d[i][i] = 0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

def main():
    n,w,l = inpm()
    d = [[10**20 for i in range(n)] for i in range(n)] 
    for _ in range(w):
        x,y,z = inpm()
        x -= 1
        y -= 1
        if z > l:
            continue
        d[x][y] = z
        d[y][x] = z
    d = warshall_floyd(d,n)
    e = [[10**20 for _ in range(n)] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            if d[i][j] <= l:
                e[i][j] = 1
                e[j][i] = 1
    q = inp()
    e = warshall_floyd(e,n)
    for _ in range(q):
        s,t = inpm()
        ans = e[s-1][t-1]
        if ans == 10**20:
            print(-1)
            continue
        print(ans-1)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from heapq import heappop, heappush
from scipy.sparse.csgraph import floyd_warshall
input = sys.stdin.readline
 
def main():
    n,w,l = map(int,input().split())
    d = [[10**15 for _ in range(n)] for _ in range(n)]
    for _ in range(w):
        x,y,z = map(int,input().split())
        x -= 1
        y -= 1
        if z > l:
            continue
        d[x][y] = z
        d[y][x] = z
    for i in range(n):
        d[i][i] = 0
    d = floyd_warshall(d)
    G = [[10**15 for _ in range(n)] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            if d[i][j] <= l:
                G[i][j] = 1
                G[j][i] = 1
    for i in range(n):
        G[i][i] = 0
    G = floyd_warshall(G)
    q = int(input())
    for _ in range(q):
        s,t = map(int,input().split())
        s -= 1
        t -= 1
        ans = G[s][t]
        if ans == 10**15:
            print(-1)
            continue
        print(int(ans)-1)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n=int(input())
L=list(map(int,input().split()))

def tri(a,b,c):
    if a<b+c and b<a+c and c<a+b:
        return 1
    else:
        return 0
count=0
for i in range(0,n-2):
    k=L[i]
    for j in range(i+1,n-1):
        t=L[j]
        for m in range(j+1,n):
            if tri(k,t,L[m])==1:
                count+=1
print(count)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
def nibuta(a,x):
    h=len(a)
    if a[0]>=x:
        return 0
    elif a[h-1]<x:
        return h
    else:
        lo=-1
        up=h-1
        while up-lo>1:
            if a[(lo+up)//2]>=x:
                up=(lo+up)//2
            else:
                lo=(lo+up)//2
        if a[up]>=x:
            return lo+1
        else:
            return up+1
s=0
for i in range(n-2):
    a1=l[i]
    for j in range(i+1,n-1):
        k=a1+l[j]
        s=s+nibuta(l[j+1:],k)
print(s)
### BUGGY CODE ###


class Node:
    def __init__(self, key=-1):
        self.key = key
        self.parent = -1
        self.left = -1
        self.right = -1
    
    def setKey(self, key):
        self.key = key


def insert(T_, z): #(T, Node)
    global T
    y = -1
    x = T_ #Node()
    while x != -1 :
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y == -1:
        T = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z


def preParse(T):
    if T == -1 :
        return
    print T.key,
    preParse(T.left)
    preParse(T.right)

def inParse(T):
    if T == -1 :
        return
    inParse(T.left) #Node() or -1
    print T.key,
    inParse(T.right)


T = -1

def main():
    com = []
    m = int(raw_input())
    for i in xrange(m):
        com.append(raw_input())
    for i in xrange(m):
        if com[i][0] == 'i':
            insert(T,Node(key=int(com[i][7:])))
        else:
            print '',
            inParse(T)
            print
            print '',
            preParse(T)
            print 
    return 0

main()
            

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
  
  
class Node(object):
    def __init__(self, key=None):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
  
  
def tree_insert(top, z):
    y = None
    x = top
    while isinstance(x, Node):
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        top = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    return top
  
  
def inorder_walk(node):
    if node.left:
        inorder_walk(node.left)
    print('', node.key, end='')
    if node.right:
        inorder_walk(node.right)
  
  
def preorder_walk(node):
    print('', node.key, end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
        preorder_walk(node.right)
  
  
n = int(stdin.readline())
  
top = None
for _ in range(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        key = int(cmd[7:])
        #assert -2000000000 <= key <= 2000000000
        top = tree_insert(top, Node(key))
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()
### BUGGY CODE ###

n,m=map(int,input().split())
memo=[]
l,r=map(int,input().split())
for i in range(r-l+1):
    memo.append(l+i)
for v in range(m-1):
    memo1=[]
    l,r=map(int,input().split())
    for k in range(len(memo)):
        if l<=memo[k]<=r:
            memo1.append(memo[k])
    memo=memo1
print(len(memo))

### FIXED CODE ###

n,m=map(int,input().split())
l=[]
r=[]
for i in range(m):
    l1,r1=map(int,input().split())
    l.append(l1)
    r.append(r1)
print(0 if min(r)-max(l)+1<0 else min(r)-max(l)+1)
### BUGGY CODE ###

s = input()
k = int(input())


ans_set = set()
for i in range(len(s)):
    c = s[i]
    ans_set.add(c)
    for j in range(i + 1, len(s)):
        c += s[j]
        ans_set.add(c)


ans_lst = list(ans_set)
ans_lst.sort()
ans = ans_lst[k-1]


print(ans)

### FIXED CODE ###

s = input()
k = int(input())


ans_set = set()
for i in range(len(s)):
    c = s[i]
    ans_set.add(c)
    for j in range(i + 1, len(s)):
        c += s[j]
        if len(c) > k:
            break
        ans_set.add(c)


ans_lst = list(ans_set)
ans_lst.sort()
ans = ans_lst[k-1]


print(ans)
### BUGGY CODE ###

a=int(input())
li = list(map(int,input().split()))
c = 0
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)

    # divisors.sort()
    return divisors

for i in range(len(li)-1):
    if len(list(set(li))) != len(li):
        c = 1
        break
    for j in range(i+1,len(li)):
        x = make_divisors(li[i])
        y = make_divisors(li[j])
        z = x + y 
        if len(x)+len(y)-1 == len(z):
            c =1
            break

if c > 0:
    print('NO')
else:
    print('YES')

### FIXED CODE ###

a=int(input())
li = list(map(int,input().split()))
c = 0
if len(li) != len(set(li)):
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

n=int(input())
m=1
inf=10**18
lol=0
l=list(map(int,input().split()))
for i in l:
  m=m*i
if(m>inf):
  print(-1)
else:
  print(m)

### FIXED CODE ###

n=int(input())
m=1
inf=10**18
lol=0
l=list(map(int,input().split()))
if 0 in l:
    print(0)
else:

    for i in l:
      m=m*i
      if(m>inf):
        lol=1
        break
    if(lol):
      print(-1)
    else:
      print(m)
### BUGGY CODE ###

def hoge():
  from itertools import permutations
  N, M, R = map(int, input().split())
  r = map(int, input().split())
  inf = float('inf')
  d = [[inf] * N for i in range(N)]

  for i in range(N):
      d[i][i] = 0

  for i in range(M):
      a, b, c = map(int, input().split())
      a -= 1
      b -= 1
      t = min(c, d[a][b])
      if d[a][b] > c:
          d[a][b], d[b][a] = t, t


  for i in range(N):
      for j in range(N):
          for k in range(N):
              d[i][j] = min(d[i][j], d[i][k] + d[k][j])


  ans = inf
  for i in permutations(r):
      temp = 0
      for j in range(len(i)-1):
          temp += d[i[j]-1][i[j+1]-1]
          if temp > ans:
              break
      ans = min(ans, temp)

  print(ans)
hoge()

### FIXED CODE ###

from itertools import permutations

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

def main():
    n, m, r = input_list()
    rlist = input_list()
    rlist = [r-1 for r in rlist]
    d = [[float('inf')]*n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    
    for i in range(m):
        a, b, c = input_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c

    for k in range(n):
        for i in range(n):
            for j in range(n):
                distance = d[i][k]+d[k][j]
                if d[i][j] > distance:
                    d[i][j] = distance

    ans = float('inf')
    for p in permutations(rlist):
        distance = 0
        for i in range(r-1):
            distance += d[p[i]][p[i+1]]

        if ans > distance:
            ans = distance

    print(ans)

main()
### BUGGY CODE ###

s = input()
a = int(s)%2019
mod_N = [0]*2019
mod_N[a] += 1
r = 10**(len(s)-1)
for i in s:
  a = (a-int(i)*10**r)%2019
  r = r//10
  mod_N[a] += 1
ans = 0
for i in mod_N:
  ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

s = input()
a = 0
mods = [0]*2019
mods[a] += 1
r = 1
for i in s[::-1]:
  a = (a+int(i)*r)%2019
  r = r*10%2019
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

s = input().split('T')
x, y = map(int, input().split())
x = abs(x-len(s[0]))
y = abs(y)
dx = []
for i in range(2, len(s), 2) :
    dx.append(len(s[i]))
dy = []
for i in range(1, len(s), 2) :
    dy.append(len(s[i]))

if sum(dx) < x or sum(dy) < y :
    print('No')
    exit()

xl = len(dx)
for i in range(1 << xl) :
    nx = 0
    for j in range(xl) :
        if i>>j & 1 :
            nx -= dx[j]
        else :
            nx += dx[j]
    if nx == x :
        break
else :
    print('No')
    exit()

yl = len(dy)
for i in range(1 << yl) :
    ny = 0
    for j in range(yl) :
        if i>>j & 1 :
            ny -= dy[j]
        else :
            ny += dy[j]
    if ny == y :
        break
else :
    print('No')
    exit()

print('Yes')

### FIXED CODE ###

s = input().split('T')
x, y = map(int, input().split())
s = [len(_) for _ in s]
dx = s[::2]
dy = s[1::2]

x = abs(x-dx[0])
y = abs(y)
dx = dx[1:]
px = 0
py = 0
for d in reversed(sorted(dx)) :
    if px > x :
        px -= d
    else :
        px += d

for d in reversed(sorted(dy)) :
    if py > y :
        py -= d
    else :
        py += d

if px == x and py == y :
    print('Yes')
else :
    print('No')
### BUGGY CODE ###

# distutils: language=c++
# cython: language_level=3, boundscheck=False, wraparound=False
# cython: cdivision=True

def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))

def main():
  n = INT()
  a = LMAPINT()

  ans = [0] * (max(a) + 1)
  for x in a:
    # 重複
    if ans[x] != 0:
      ans[x] = 2
    else:
      for j in range(x, max(a)+1, x):
        ans[j] += 1
  
  print(len(list(filter(lambda x: ans[x] == 1, a))))


if __name__ == '__main__':
  main()

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
xs = [0] * (max(a) + 1)
 
for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))
### BUGGY CODE ###

def main():
    n=int(input())
    aa=input().split()
    x=1
    for a in aa:
        x*=int(a)
    if x>1000000000000000000:
        print(-1)
    else:
        print(x)
main()

### FIXED CODE ###

def main():
    n=int(input())
    aa=map(int,input().split())
    x=1
    for a in aa:
        if a == 0:
            print(0)
            return
        if x<1000000000000000000:
            x*=a
    if x>1000000000000000000:
        print(-1)
    else:
        print(x)
main()
### BUGGY CODE ###

a = [i for i in range(int(input()))]
print(sum(a))

### FIXED CODE ###

b = int(input())
if b % 2 == 1:
    print((b-1) * ((b-1) // 2) + ((b-1) // 2))
else:
    print((b - 1) * ((b-1) // 2 + 1))
### BUGGY CODE ###

#common subsequence
n,m=map(int,input().split())
mod=10**9+7
a=list(map(int,input().split()))
b=list(map(int,input().split()))
dp=[[0 for i in range(m+1)] for j in range(n+1)]
#dp[i][j]=aのi番目、bのj番目まででの個数
#求めたいのはdp[n][m]
for i in range(m+1):
    dp[0][i]=1
for i in range(n+1):
    dp[i][0]=1
dp[0][0]=1
for i in range(1,n+1):
    for j in range(1,m+1):
        if a[i-1]==b[j-1]:
            dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod
        else:
            dp[i][j]=(dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1])%mod
print(dp[n][m])

### FIXED CODE ###

#common subsequence
n,m=map(int,input().split())
mod=10**9+7
a=list(map(int,input().split()))
b=list(map(int,input().split()))
dp=[[0 for i in range(m+1)] for j in range(n+1)]
#dp[i][j]=aのi番目、bのj番目まででの個数
#求めたいのはdp[n][m]
for i in range(m+1):
    dp[0][i]=1
for i in range(n+1):
    dp[i][0]=1
dp[0][0]=1
for i in range(1,n+1):
    for j in range(1,m+1):
        if a[i-1]==b[j-1]:
            dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod
        else:
            dp[i][j]=(dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1])%mod
print(dp[n][m])
### BUGGY CODE ###

from collections import Counter

n = int(input().strip())

count_by_kw = Counter()
c=0
for i in range(n):
    s=str(sorted(input().strip()))
    if s in count_by_kw:
        c+=count_by_kw[s]
    count_by_kw[s]+=1
    
print(c)

### FIXED CODE ###

n = int(input().strip())

count_by_kw = {}
for i in range(n):
    s=''.join(sorted(input().strip()))
    if s in count_by_kw.keys():
        count_by_kw[s]+=1
    else:
        count_by_kw[s]=1

c=list(count_by_kw.values())
ans=0
for val in c:
    ans+=val*(val-1)//2

print(ans)
### BUGGY CODE ###

n = int(input())
import sys

def ato(x):
    if x == "Male":
        return 0
    elif x == "Female":
        return 1
    else:
        return -1
    
print(0)
s0 = ato(input())
if s0 == -1:
    sys.exit()
    
print(n-1)
s1 = ato(input())
if s1 == -1:
    sys.exit()
    
left = 0
right = n-1
center = (left+right) // 2
while right - left >= 1:
    center = (left+right) // 2
    
    print(center)
    s2 = ato(input())
    if s2 == -1:
        break
    
    if (center - left)%2 != abs(s2 - s0):
        right = center - 1
        s1 = s2
    else:
        left = center + 1
        s0 = s2

### FIXED CODE ###

n = int(input())
import sys

def ato(x):
    if x == "Male":
        return 0
    elif x == "Female":
        return 1
    else:
        return -1
    
print(0)
s0 = ato(input())
if s0 == -1:
    sys.exit()
    
print(n-1)
s1 = ato(input())
if s1 == -1:
    sys.exit()
    
left = 0
right = n-1
center = (left+right) // 2
while True:
    center = (left+right) // 2
    
    print(center)
    s2 = ato(input())
    if s2 == -1:
        break
    
    if (center - left)%2 == abs(s2 - s0):
        left = center
        s0 = s2
    else:
        right = center
        s1 = s2
### BUGGY CODE ###

N, Q = map(int, input().split())
s = input()
td = []
for i in range(Q):
    td.insert(0, input().split())

#print("td = {}".format(td))

llim = 0
rlim = N - 1
for t, d in td:
    if((s[llim] == t) & ("L" == d)):
        llim += 1
    if((s[rlim] == t) & ("R" == d)):
        rlim -= 1
#    print("td = {}, llim = {}, rlim = {}".format([t, d], llim, rlim))

if(llim > rlim):
    print("0")
else:
    print(str(rlim - llim + 1))


### FIXED CODE ###

N, Q = map(int, input().split())
s = " " + input() + " "
td = []
for i in range(Q):
    td.append(input().split())
#print("td = {}".format(td))

llim = 0
rlim = N + 1
for t, d in reversed(td):
    if((s[llim + 1] == t) and ("L" == d)):
        llim += 1
    elif((s[llim] == t) and ("R" == d)):
        llim -= 1
    if((s[rlim - 1] == t) and ("R" == d)):
        rlim -= 1
    elif((s[rlim] == t) and ("L" == d)):
        rlim += 1
#    print("td = {}, llim = {}, rlim = {}".format([t, d], llim, rlim))

print(str(max(0, rlim - llim - 1)))
### BUGGY CODE ###

T = input()
T_l = [t for t in T]
#print(T_l)
out = []
i = 0
while(i < len(T)):
  if T_l[i] == "?":
    if (i+1 != len(T)) & (i-1 != -1):
      if T_l[i+1]=="D": 
        out.append("P")
        i += 1
      elif T_l[i-1]=="P": 
        out.append("D")
        i += 1
      elif T_l[i+1]=="?":
        out.append("PD")
        i += 2

    elif (i+1 == len(T)):
      out.append("D")
      i += 1

    elif (i-1 == -1):
      if T_l[i+1]=="D": 
        out.append("P")
        i += 1
      elif T_l[i+1]=="P": 
        out.append("D")
        i += 1
      elif T_l[i+1]=="?":
        out.append("PD")
        i += 2

  else:
    out.append(T_l[i])
    i += 1

  #print(out)

print("".join(out))


### FIXED CODE ###

T = input()
T_l = [t for t in T]

for i in range(len(T_l)):
  if T[i] =="?": T_l[i] = "D"

print("".join(T_l))
### BUGGY CODE ###

A, B, M = (int(x) for x in input().split())
al = [int(x) for x in input().split()]
bl = [int(x) for x in input().split()]
ml = [[int(x) for x in input().split()] for _ in range(M)]
"""
price = []
for l in ml:
    price.append(al[l[0]-1] + bl[l[1]-1] - l[2])
for x in al:
    for y in bl:
        price.append(x+y)
"""
price = [al[l[0]-1] + bl[l[1]-1] - l[2] for l in ml] + [x + y for x in al for y in bl] 
print(min(price))

### FIXED CODE ###

A, B, M = (int(x) for x in input().split())
al = [int(x) for x in input().split()]
bl = [int(x) for x in input().split()]
ml = [[int(x) for x in input().split()] for _ in range(M)]
"""
price = []
for l in ml:
    price.append(al[l[0]-1] + bl[l[1]-1] - l[2])
for x in al:
    for y in bl:
        price.append(x+y)
"""
price = [al[l[0]-1] + bl[l[1]-1] - l[2] for l in ml] + [min(al)+min(bl)] 
print(min(price))
### BUGGY CODE ###

def solve():
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    dp = set([0])
    for i in range(N-1,-1,-1):
        if S[i]=='0':
            add = set()
            for a in dp:
                add.add(a^A[i])
            dp |= add
        else:
            if A[i] not in dp:
                dp = set()
    if len(dp) != 0:
        ans = '0'
    else:
        ans = '1'
    print(ans)

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

### FIXED CODE ###

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

if __name__ == '__main__':
    main()