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

from collections import deque
 
h,w=[int(x) for x in input().rstrip().split()]
l=[[s for s in input()]for i in range(h)]

black=sum(s.count("#") for s in l)
dist=[[False for j in range(w)] for i in range(h)]
done=[[float('inf') for j in range(w)] for i in range(h)]
move=[[1,0],[-1,0],[0,1],[0,-1]]

def bfs():
  stack=deque([[0,0]])
  done[0][0]=0
  while(stack):
    x,y=stack.popleft()
    dist[y][x]=True
    
    for dx,dy in move:
      mx,my=x+dx,y+dy
      if (0<=my<=h-1) and (0<=mx<=w-1) and l[my][mx]=="." and dist[my][mx]==False:
        done[my][mx]=done[y][x]+1
        stack.append([mx,my])
  return done[h-1][w-1]
 
if bfs()!=float('inf'):print(h*w-done[h-1][w-1]-black-1)
else:print(-1)


### FIXED CODE ###

import sys
 
h,w=[int(x) for x in input().rstrip().split()]
l=[]
black=0
for i in range(h):
  s=[x for x in input()]
  l.append(s)
  black+=sum(j.count("#") for j in s)
 
done=[[float('inf')]*w for i in range(h)]
def bfs():
  stack=[[0,0]]
  done[0][0]=0
  while(stack):
    x,y=stack.pop(0)
    move=[[x+1,y],[x-1,y],[x,y+1],[x,y-1]]
 
    for mx,my in move:
      if not(0<=my<=h-1) or not(0<=mx<=w-1) or l[my][mx]=="#" or done[my][mx]!=float('inf'):
        continue

      done[my][mx]=done[y][x]+1
      stack.append([mx,my])
      
      if my==h-1 and mx==w-1:
        print(h*w-done[my][mx]-black-1)
        sys.exit()
  print(-1)
 
if __name__=="__main__":
  bfs()
### BUGGY CODE ###

N=int(input())
s=[]
for i in range(N):
    s.append(input())

su=[]
for i in s:
    shu=sorted(list(i))
    su.append("".join(shu))


count=0
while len(su)>0:
  j=su[0]
  del su[0]
  c=su.count(j)+1
  count+=c*(c-1)/2
  su=[i for i in su if i!=j]
  
print(int(count))

### FIXED CODE ###

import collections
N=int(input())
su=["".join(sorted(list(input()))) for _ in range(N)]

C=list(collections.Counter(su).values())

ans=0
for i in C:
  if i>1:
    ans+=i*(i-1)//2

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

n,m = (int(i) for i in input().split())
p,y =[],[]
for i in range(m):
    tmp = list(int(i) for i in input().split())
    p.append(tmp[0])
    y.append(tmp[1])

dict = {}
for i in range(m):
    if not p[i] in dict.keys():
        dict[p[i]] = [(y[i],i)]
    else:
        dict[p[i]].append((y[i],i))

for k,v in dict.items():
  dict[k] = sorted(v)

for i in range(m):
  for k,v in dict.items():
    for j in range(len(v)):
        if i == v[j][1]:
            id = '0'*(6-len(str(k)))+str(k)
            id = id + '0'*(6-len(str(j)))+str(j+1)
            print(id)


### FIXED CODE ###

N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]

cs = [[] for i in range(N+1)]
for i,(p,y) in enumerate(src):
    cs[p].append((y,i))
for cc in cs:
    cc.sort()

ans = [None] * M
for p in range(len(cs)):
    for i,(_,j) in enumerate(cs[p]):
        s = str(p).zfill(6) + str(i+1).zfill(6)
        ans[j] = s
print(*ans, sep='\n')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	A = input().split(" ")
	A = list(A)
	#A = A[:-1]
	A = [int(s) * (-1) for s in A]
	heapq.heapify(A)

	for i in range(M):
		b, c = map(int, input().split(" "))
		for _ in range(b):
			heapq.heappush(A, c * (-1))
	
	ans = 0
	for i in range(N):
		tmp = heapq.heappop(A) * (-1)
		ans += tmp
		#print(tmp)
	print(ans)

if __name__ == "__main__":
	main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	A = input().split(" ")
	A = list(A)
	#A = A[:-1]
	A = [(int(s) * (-1), 1) for s in A]
	heapq.heapify(A)

	for i in range(M):
		b, c = map(int, input().split(" "))
		heapq.heappush(A, (c * (-1), b))
	
	ans = []
	for i in range(N):
		t, con = heapq.heappop(A)
		for _ in range(con):
			if len(ans) == N:
				print(sum(ans))
				sys.exit()
			ans.append(t * (-1))
	print(sum(ans))


if __name__ == "__main__":
	main()
### BUGGY CODE ###

# https://atcoder.jp/contests/dwacon6th-prelims/submissions/9425560
# 部分点解法

def main():
    from functools import reduce

    MOD = 10 ** 9 + 7

    n = int(input())
    *x, = map(int, input().split())

    fact = [1]
    for i in range(1, n + 1):
        fact.append(fact[-1] * i)

    dist_to_r_edge = [x[-1] - x_ for x_ in x[:-1]]

    ret = reduce(
        lambda a, b: (a + b) % MOD,
        (
            d * pow(i, MOD - 2, MOD)
            for i, d in enumerate(dist_to_r_edge, 1)
        )
    )
    print(ret * fact[n - 1] % MOD)


if __name__ == '__main__':
    main()

# ret = 0
# for i, d in enumerate(dist_to_r_edge, 1):
#     ret = (ret + d * pow(i, MOD - 2, MOD)) % MOD
# print(ret * fact[n - 1] % MOD)


### FIXED CODE ###

def main():
    from itertools import accumulate

    MOD = 10 ** 9 + 7
    n = int(input())
    *x, = map(int, input().split())
    y = [b - a for b, a in zip(x[1:], x)]

    csum_invs = [0] + list(accumulate([pow(i, MOD - 2, MOD) for i in range(1, n + 1)]))
    # csum_invs = [0]
    # t = 0
    # for i in range(1, n + 1):
    #     t += pow(i, MOD - 2, MOD)
    #     t %= MOD
    #     csum_invs.append(t)

    fact = [0]
    t = 1
    for i in range(1, n + 1):
        t *= i
        t %= MOD
        fact.append(t)

    ret = 0
    for j, y_ in enumerate(y, 1):
        ret = (ret + csum_invs[j] * y_) % MOD
    print((ret * fact[n - 1]) % MOD)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

S, C = map(int,input().split())
ans = 0

flag = True
while flag:
  if S >= 1 and C >= 2:
    S -= 1
    C -= 2
  elif C >= 4:
    C -= 4
  else:
    break
  ans += 1
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
ans = 0

if M <= 1:
    ans = 0

elif N >= M:
    ans = M//2

elif N < M:
    if N*2 >= M:
        ans = M//2
    else:
        ans += N
        ans += (M-N*2)//4
print(ans)
### BUGGY CODE ###

n,x,y = map(int,input().split())
ps = []
for i in range(n):
    for j in range(i):
        ps.append([j+1,i+1])

dists = [0]*(n)
for p in ps:
    dist = min(abs(p[0]-p[1]),abs(p[0]-x)+1+abs(p[1]-y),abs(p[1]-x)+1+abs(p[0]-y))
    dists[dist] = dists[dist]+1

for i in range(len(dists) - 1):
    print(dists[i+1])

### FIXED CODE ###

n,x,y = map(int,input().split())
dists = [0]*(n)
for i in range(1,n+1):
    for j in range(1,i):
        dist = min(abs(i-j),abs(i-x)+1+abs(j-y),abs(j-x)+1+abs(i-y))
        dists[dist] = dists[dist]+1
    
for i in range(len(dists) - 1):
    print(dists[i+1])
### BUGGY CODE ###

n = int(input())
A = sorted(list(map(int, input().split())))
flags = [1] * n
for i, a in enumerate(A):
    if flags[i]:
        for j, f in enumerate(flags[i+1:], i+1):
            if a == A[j]:
                flags[i] = 0
                flags[j] = 0
            if A[j] % a == 0:
                flags[j] = 0
print(sum(flags))

### FIXED CODE ###

n = int(input())
A = sorted(list(map(int, input().split())))
M = 10**6 + 1
L = [0]*M
for a in A:
    L[a] += 1
    if L[a] == 1:
        # k>=2として k*aは全て不適
        for i in range(2*a, M, a):
            L[i] += 2
# flagの数が答え
print(L.count(1))
### BUGGY CODE ###

N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = []
for _m in range(M):
    path = input().strip().split(' ')
    path = int(path[0]), int(path[1])
    path = path if path[0] < path[1] else (path[1], path[0])
    if path not in paths:
        paths.append(path)
all_paths = []
for path in paths:
    all_paths += path
all_paths = set(all_paths)
count = 0
for n in range(1, N+1):
    is_good = 1
    if n not in all_paths:
        count += is_good
        continue

    for path in paths:
        if n not in list(path):
            continue
        if (path[0] == n) and (H[n-1] <= H[path[1]-1]):
            is_good = 0
            break
        if (path[1] == n) and (H[n-1] <= H[path[0]-1]):
            is_good = 0
            break    
    count += is_good
print(count)

### FIXED CODE ###

N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = []
max_neighbor = [ 0 for _ in range(N)]

for _m in range(M):
    path = input().strip().split(' ')
    path = int(path[0]), int(path[1])
    max_neighbor[path[0]-1] = max(max_neighbor[path[0]-1], H[path[1]-1])
    max_neighbor[path[1]-1] = max(max_neighbor[path[1]-1], H[path[0]-1])
count = 0
for n in range(N):
    if max_neighbor[n] < H[n]:
        count += 1
print(count)
### BUGGY CODE ###

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

L.sort(reverse=True)

s = 0
for i in range(N):
    o = []
    for j in range(i+1,N):
        for k in range(j+1,N):
            o.append(L[j]+L[k])
    o.sort()
    o = [0] + o + [3000]
    key = L[i]
    l = 0
    r = len(o)-1
    while r - l > 1:
        m = (r + l) // 2
        if o[m] > key:
            r = m
        else:
            l = m
    #print(key,o,l,len(o))
    s += len(o)-l-2

print(s)

### FIXED CODE ###

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

L.sort()

s = 0

ma = L[N-1]
for j in range(N-2):
    ja = L[j]
    for k in range(j+1,N-1):
        ka = L[k]
        # L[i] < L[j]+L[k] となる L[i]の数を求める
        key = ja + ka
        l = k + 1
        r = N - 1
        while r - l > 1:
            m = l + (r - l) // 2
            if L[m] < key:
                l = m
            else:
                r = m
        kka = L[k+1]
        if kka < key <= ma:
            s += l-k
        elif key <= kka:
            s += 0
        else:
            s += N-k-1

print(s)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

s = input()
k = ni()
li = []
for i in range(len(s)):
    for j in range(i, i+k+1):
        t = s[i:j+1]
        if t not in li:
            li.append(s[i:j+1])
li.sort()
print(li[k-1])

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

s = input()
k = ni()
li = []
for i in range(len(s)):
    for j in range(i, i+k+1):
        li.append(s[i:j+1])
li = list(set(li))
li.sort()
print(li[k-1])
### BUGGY CODE ###

def main():
    from collections import Counter

    s = str(input())
    num = ""
    li = []
    f = 0
    mi = 0
    li_append = li.append

    cm = {}
    for i in range(1,2*(10 ** 5)):
        cm[i] = i * (i - 1) // 2
    cm[0] = 0



    for i in range(1, len(s) + 1):
        num = s[-i] + num
        li_append(int(num) % 2019)
        if num[0] == "0":
            f += 1
        else:
            mi += cm[f+1]
            f = 0

    co = Counter(li)
    co_1 = Counter(co.values())
    ans_1 = 0

    for x in co_1.keys():
        if x != 1:
            ans_1 += cm[x]* co_1[x]
    ans2 = 0
    if 0 in co:
        ans2 = co[0]
    print(ans_1 + ans2 - mi)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    dic = defaultdict(int)

    input = sys.stdin.readline

    s = str(input().rstrip())
    m = 0
    before_m = 0.1

    for i in range(1, len(s) + 1):
        before_m = int(before_m*10)%2019
        m_ad = (int(s[-i]) * before_m) % 2019
        m = (m_ad + m) % 2019
        dic[m] += 1

    ans1 = 0

    for x in dic.values():
        if x > 1:
            ans1 += x * (x - 1) // 2
    ans2 = dic[0]

    print(ans1 + ans2)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def main():
    N,W = map(int, input().split())
    w = []
    v = []
    for _ in range(N):
        x,y = map(int, input().split())
        w.append(x)
        v.append(y)

    dp = [[0]*(W+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            if j - w[i] >= 0:
                dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i])
            else:
                dp[i+1][j] = dp[i][j]
                
    ans = 0
    for a in dp:
        ans = max(ans, max(a))
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    N,W = map(int, input().split())
    w = []
    v = []
    for _ in range(N):
        x,y = map(int, input().split())
        w.append(x)
        v.append(y)

    dp = [[0]*(W+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            if j - w[i] >= 0:
                dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i])
            else:
                dp[i+1][j] = dp[i][j]
                
    ans = 0
    for a in dp:
        ans = max(ans, max(a))
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

def func(num,arr):
  dp=[1]*(n+1)
  dp[0]=(1-arr[0])
  dp[1]=arr[0]
  for i in range(1,n):
    dp[i+1]=dp[i]*arr[i]
    for j in range(1,i+1):
      dp[i+1-j]=dp[i-j]*arr[i]+dp[i+1-j]*(1-arr[i])
    dp[0]=dp[0]*(1-arr[i])
  return dp

n=int(input())
arr=list(map(float,input().split()))
dp=func(n,arr)
ans=0
for i in range(int(n/2)+1,n+1):
  ans+=dp[i]
print(ans)

### FIXED CODE ###

n=int(input())
arr=list(map(float,input().split()))
dp=[1]*(n+1)
dp[0]=(1-arr[0])
dp[1]=arr[0]
for i in range(1,n):
  for j in range(i+2):
    if j==0:
      dp[i+1-j]=dp[i-j]*arr[i]
    elif j==i+1:
      dp[i+1-j]=dp[i+1-j]*(1-arr[i])
    else:
      dp[i+1-j]=dp[i-j]*arr[i]+dp[i+1-j]*(1-arr[i])
ans=0
for i in range(int(n/2)+1,n+1):
  ans+=dp[i]
print(ans)
### BUGGY CODE ###

from collections import defaultdict
h, w, m = map(int, input().split())
targets = defaultdict(int)
targets_count_yoko = defaultdict(int)
targets_count_tate = defaultdict(int)
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    targets_count_yoko[x] += 1
    targets_count_tate[y] += 1
    targets[(y, x)] = -1

max_row = max(targets_count_yoko.values())
max_line = max(targets_count_tate.values())
y_idx = []
x_idx = []
for i in range(w):
    if targets_count_yoko[i] == max_row:
        x_idx.append(i)
for i in range(h):
    if targets_count_tate[i] == max_line:
        y_idx.append(i)


ans = 0
for y in y_idx:
    for x in x_idx:
        res = max_line + max_row + targets[(y, x)]
        ans = max(ans, res)

print(ans)


### FIXED CODE ###

from collections import defaultdict
h, w, m = map(int, input().split())
targets = defaultdict(int)
targets_count_yoko = defaultdict(int)
targets_count_tate = defaultdict(int)
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    targets_count_yoko[x] += 1
    targets_count_tate[y] += 1
    targets[(y, x)] = -1

max_row = max(targets_count_yoko.values())
max_line = max(targets_count_tate.values())
y_idx = defaultdict(bool)
x_idx = defaultdict(bool)
max_count_x = 0
max_count_y = 0
for i in range(w):
    if targets_count_yoko[i] == max_row:
        x_idx[i] = True
        max_count_x += 1
for i in range(h):
    if targets_count_tate[i] == max_line:
        y_idx[i] = True
        max_count_y += 1


ans = max_line + max_row
kumi = max_count_x*max_count_y
for key_y, key_x in targets.keys():
    if y_idx[key_y] and x_idx[key_x]:
        kumi -= 1
    if kumi == 0:
        break

if kumi == 0:
    print(ans-1)
else:
    print(ans)
### BUGGY CODE ###

import numpy as np
from itertools import product

H,W,K = map(int, input().split())
S = np.array(([list(map(int,list(input()))) for _ in range(H)])).T

if np.sum(S)<=K:
    print(0)
else:
    answer = H * W
    for X in product([False,True], repeat=H-1):
        ans = np.sum(X)
        if ans >= answer:
            continue
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])
            M[-1].append(i+1)
        D = np.zeros(len(M))
        for s in S:
            D[:] += [sum(s[i] for i in m) for m in M]
            if any(d > K  for d in D):
                ans += 1
                if ans >= answer:
                    break
                D[:] = [sum(s[i] for i in m) for m in M]

        if answer > ans:
            answer = ans

    print(min(answer,ans))

### FIXED CODE ###


def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()
### BUGGY CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_g
import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        # n: num of vertices
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfsWithDp(self, node, dp, visited):
        visited[node] = True
        for i in range(len(self.adj[node])):
            child = self.adj[node][i]
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  # dp[i] := longest path starting from vertex i
        for i in range(self.n):
            if not visited[i]:
                self.dfsWithDp(i, dp, visited)
        return max(dp)


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    print(dag.findLongestPathWithDp())


main()


### FIXED CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_g
import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        # n: num of vertices
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfsWithDp(self, node, dp, visited):
        if(visited[node]):
            return dp[node]
        visited[node] = True
        for child in self.adj[node]:
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  # dp[i] := longest path starting from vertex i
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithDp(i, dp, visited))
        return ans


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    print(dag.findLongestPathWithDp())


main()
### BUGGY CODE ###

# DAGの最長経路...トポロジカルソートもどきか？
# 普通にDAGに沿ったdpをすればいいのでは?
# 再帰だと実装楽そうだけどどうしよう
# 問題は終了と最初がわからんこと
# いや最初は全部長さ0をセットすればいいだろ
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

N, M = ints()
dag = defaultdict(lambda: [])
indeg = [0] * N
for _ in ra(M):
    x, y = mina(*ints())
    indeg[y] += 1
    dag[x].append(y)

q = deque()
for u, inn in enu(indeg):  # 多点DFS初期化
    if inn == 0:
        q.append(u)  # 別にlengthの情報をもたせちゃってもいいんだけどね

dp = [0] * N
while q:  # トポロジカル順序でdpテーブルを埋めていく
    u = q.popleft()
    for nx in dag[u]:
        dp[nx] = max(dp[nx], dp[u] + 1)
        # indeg[nx] -= 1
        # if indeg[nx] == 0:
        q.append(nx)
print(max(dp))


### FIXED CODE ###

# DAGの最長経路...トポロジカルソートもどきか？
# 普通にDAGに沿ったdpをすればいいのでは?
# 再帰だと実装楽そうだけどどうしよう
# 問題は終了と最初がわからんこと
# いや最初は全部長さ0をセットすればいいだろ
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

N, M = ints()
dag = defaultdict(lambda: [])
indeg = [0] * N
for _ in ra(M):
    x, y = mina(*ints())
    indeg[y] += 1
    dag[x].append(y)

q = deque()
for u, inn in enu(indeg):  # 多点DFS初期化
    if inn == 0:
        q.append(u)

dp = [0] * N
while q:  # トポロジカル順序でdpテーブルを埋めていく
    u = q.popleft()
    # dp[u] = max(dp[u], l)
    for nx in dag[u]:
        dp[nx] = max(dp[nx], dp[u] + 1)
        indeg[nx] -= 1
        if indeg[nx] == 0:
            q.append(nx)
print(max(dp))
### BUGGY CODE ###

T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    DP = [set() for _ in range(N+1)]
    DP[N].add(0)
    for i in range(N-1, -1, -1):
        if S[i] == '0':
            for x in DP[i+1]:
                DP[i].add(x)
                DP[i].add(x ^ A[i])
        else:
            if A[i] in DP[i+1]:
                for x in DP[i+1]:
                    DP[i].add(x)

    if 0 in DP[0]:
        print(0)
    else:
        print(1)

### FIXED CODE ###

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)