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

import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))


# 条件を満たすかどうか
def is_ok(l, i, key):
    # ここが条件
    if l[i] >= key:
        return True


def binary_seach(l, key) -> int:
    left = -1
    right = len(l)

    while right - left > 1:
        mid = left + (right - left) // 2
        if is_ok(l, mid, key):
            right = mid
        else:
            left = mid

    return right


n = I()
l = LI()
l = sorted(l)
ans = 0
for i in range(n - 2):
    # 三角形のうち一番短い辺
    a = l[i]
    for j in range(i + 1, n - 1):
        # 三角形のうち二番目に短い辺
        b = l[j]
        # 三角形の中で一番大きい辺 かつ
        # a + b より小さい辺 を二分探索で探す
        # a + b 以上の要素の初めのindexを取得
        ind = binary_seach(l, a + b)
        # b 以上の辺のうち、a + b より小さい要素の数を足す
        ans += ind - j - 1
print(ans)


### FIXED CODE ###

import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))


# 条件を満たすかどうか
def is_ok(l, i, key):
    # ここが条件
    if l[i] >= key:
        return True


def binary_seach(l, key) -> int:
    left = -1
    right = len(l)

    while right - left > 1:
        mid = left + (right - left) // 2
        if is_ok(l, mid, key):
            right = mid
        else:
            left = mid

    return right


n = I()
l = LI()
l = sorted(l)
ans = 0
for i in range(n - 2):
    # 三角形のうち一番短い辺
    a = l[i]
    for j in range(i + 1, n - 1):
        # 三角形のうち二番目に短い辺
        b = l[j]
        # 三角形の中で一番大きい辺 かつ
        # a + b より小さい辺 を二分探索で探す
        # a + b 以上の要素の初めのindexを取得
        ind = binary_seach(l, a + b)
        # b 以上の辺のうち、a + b より小さい要素の数を足す
        ans += ind - j - 1
print(ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
s = input().rstrip() + "#"

dic = {"R": deque(), "G":deque(), "B":deque()}

prev_ch = s[0]
cnt = 1
ans = 1
for i, ch in enumerate(s[1:]):
    if ch == prev_ch:
        cnt += 1
    else:
        dic[prev_ch].append([cnt, i-1])
        while dic["R"] and dic["G"] and dic["B"]:
            r = dic["R"].popleft()
            g = dic["G"].popleft()
            b = dic["B"].popleft()
            while(r[0] and g[0] and b[0]):
                ans *= r[0] * g[0] * b[0] // cnt
                r[0] -= 1; g[0] -= 1; b[0] -= 1
                cnt -= 1
            if r[0]:
                dic["R"].appendleft(r)
            if g[0]:
                dic["G"].appendleft(g)
            if b[0]:
                dic["B"].appendleft(b)
        cnt = 1
    prev_ch = ch
for i in range(n):
    ans *= (i+1)
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())
s = input().rstrip()
MOD = 998244353

r = 0; g = 0; b = 0
rg = 0
gb = 0
br = 0
ans = 1
for ch in s:
    if ch == "R":
        if gb > 0:
            ans *= gb
            gb -= 1
        elif g > 0:
            ans *= g
            g -= 1
            rg += 1
        elif b > 0:
            ans *= b
            b -= 1
            br += 1
        else:
            r += 1
    elif ch == "G":
        if br > 0:
            ans *= br
            br -= 1
        elif b > 0:
            ans *= b
            b -= 1
            gb += 1
        elif r > 0:
            ans *= r
            r -= 1
            rg += 1
        else:
            g += 1
    elif ch == "B":
        if rg > 0:
            ans *= rg
            rg -= 1
        elif g > 0:
            ans *= g
            g -= 1
            gb += 1
        elif r > 0:
            ans *= r
            r -= 1
            br += 1
        else:
            b += 1
    ans %= MOD
for i in range(n):
    ans *= i+1
    ans %= MOD
print(ans)
### BUGGY CODE ###

N = int(input())
a = [int(x) for x in input().split()]
b = []
for ind,i in enumerate(a):
    if(ind%2==0):
        b.append(i)
    else:
        b.insert(0,i)
if(N%2!=0):
    b.reverse()
for i in b[:-1]:
    print(i,end=' ')
print(b[-1])

### FIXED CODE ###

N = int(input())
a = [int(x) for x in input().split()]

if(N==1):
    print(a[0])
elif(N%2==0):
    for i in range(N-1,-1,-2):
        print(a[i],end=' ')
    for i in range(0,N-2,+2):
        print(a[i],end=' ')
    print(a[N-2])
else:
    for i in range(N-1,-1,-2):
        print(a[i],end=' ')
    for i in range(1,N-2,+2):
        print(a[i],end=' ')
    print(a[N-2])
### BUGGY CODE ###

S = list(input().rstrip())

count = 0
flag = True
while flag:
    for i in range(len(S)-1):
        if S[i] == 'B' and S[i+1] == 'W':
            S[i], S[i+1] = S[i+1], S[i]
            count += 1
            break
        
        if i == len(S)-2:
            flag = False

print(count)

### FIXED CODE ###

S = list(input().rstrip())

ans = 0
countw = 0
for i, c in enumerate(S):
    if c == 'W':
        ans += i - countw
        countw += 1

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

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -((-t)//A), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count > K:
            return False
    return (count < K)
        

l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

print(r)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.readline

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)
mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))
CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
C,D = zip(*CD)
C = [min(c,mc) for c in C]

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,S,1)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    t, w, v = heappop(dq)
    if ans[v][w] < t:
        continue
    ans[v][w] = t
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nw,nv))

for i in range(2,N+1):
    print(min(ans[i]))





### FIXED CODE ###

from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.readline

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)

'''
from itertools import combinations 
N = 14
M = N*(N-1)//2
S = 0
UVAB = [[x,y,50,10**9] for x,y in combinations(range(1,N+1),2)] 
U,V,A,B = zip(*UVAB)
'''

mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))

CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
#CD = [[0,0]] + [[10**9,10**9] for i in range(N)]
C,D = zip(*CD)
C = [min(c,mc) for c in C]

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,S,1)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    t, w, v = heappop(dq)
    if ans[v][w] <= t:
        continue
    for i in range(w+1):
        ans[v][i] = min(t, ans[v][i])
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nw,nv))

for i in range(2,N+1):
    print(min(ans[i]))
### BUGGY CODE ###

n,q=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
#n=6
#q=2
ab = [list(map(int, input().split())) for _ in range(n-1)]
#ab=[[1,2],[1,3],[2,4],[3,6],[2,5]]
px = [list(map(int, input().split())) for _ in range(q)]
#px=[[1,10],[1,10]]
#print(ab)
#print(px)
ans= [[0 for i in range(n)] for i in range(n)]
ans2= [0 for i in range(n)]
a=[]
for i in range(n):
    ans[i][i] = 1
for i in range(len(ab)):
    ans[ab[i][0]-1][ab[i][1]-1]+=1
    a.append(ab[i][0]-1)
a=set(a)
a=sorted(a, reverse=True)
#print(a)
for i in a:
    for j in range(i+1,n):
        if(ans[i][j]>0):
            for k in range(j,n):
                ans[i][k]+=ans[j][k]
for i in range(q):
    for j in range(n):
        ans2[j]+=px[i][1]* 1 if ans[px[i][0]-1][j] else 0
print(" ".join(list(map(str,ans2))))

### FIXED CODE ###

import collections

N,Q=map(int,input().split())
M=[[] for i in range(N+1)]
P=[0 for i in range(N+1)]
for i in range(N-1):
  a,b=map(int,input().split())
  M[a].append(b)
  M[b].append(a)
#print("M:",M)

S=[0 for i in range(N+1)]
for i in range(Q):
  p,x=map(int,input().split())
  S[p]+=x
#print(S)
  
d=collections.deque([1])

while len(d):
  dd=d.popleft()
  if P[dd]==0:
    P[dd]=1
    for i in M[dd]:
      if P[i]==0:
        S[i]+=S[dd]
      d.append(i)
  #print(d,S)
print(*S[1:])
### BUGGY CODE ###

# D
N, K = map(int, input().split())
lst = list(map(int, input().split()))
ma = 0
for i in range(len(lst)-(K-1)):
    if (ma < sum(lst[i:i+K])):
        ma = sum(lst[i:i+K])
print((ma + K) / 2)


### FIXED CODE ###

# D
N, K = map(int, input().split())
lst = list(map(int, input().split()))
lst1 = [(lst[0] + 1) / 2]
ma = 0
for i in range(1, len(lst)):
    lst1.append(lst1[i-1] + ((lst[i]+1) / 2))
    if (i >= K):
        ma = max(ma,lst1[i] - lst1[i-K])
ma = max(ma,lst1[K-1])
print(ma)
### BUGGY CODE ###

N,M=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]

_A=[sum(A[:i:])%M for i in range(N+1)]

count=0





for i in set(_A):
    _count=_A.count(i)

    count+=(_count-1)*_count/2
print(int(count))


### FIXED CODE ###

N,M=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]

_A=[0]
sum=0
d={0:1}
key=[0]
for i in range(N):
    sum=(sum+A[i])%M
    try:
        d[sum]+=1
    except KeyError:
        d[sum]=1
        key.append(sum)

count=0
for i in key:
    _count=d[i]

    count+=(_count-1)*_count/2
print(int(count))
### BUGGY CODE ###

N = int(input())
a = [0]*N
for i in range(N):
    a[i] = int(input())
    
for j in range(N):
    num = a.pop(j)
    print(max(a))
    a.insert(j, num)

### FIXED CODE ###

N = int(input())
a = [0]*N
for i in range(N):
    a[i] = int(input())
b = sorted(a)   

for i in range(N):
    if(a[i] == b[N-1]):
        print(b[N-2])
    else:
        print(b[N-1])
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
print(n *(n-1)//2)
### BUGGY CODE ###

N,K=map(int,input().split())
res=0
for i in range(N):
  tmp=1
  cnt=i
  while cnt<K:
    cnt*=2
    tmp/=2
  res+=tmp
res/=N
print(res)
  


### FIXED CODE ###

N,K=map(int,input().split())
ans=0
for i in range(1,N+1):
  cnt=i
  pro=1
  while cnt<K:
    cnt*=2
    pro/=2
  pro/=N
  #print(pro)
  ans+=pro
print(ans)
### BUGGY CODE ###

import queue
h,w = map(int,input().split())
q = queue.Queue()
A = ["" for i in range(h)]
for i in range(h):
    b = input()
    A[i] = b
#    print(b)
    for j in range(w):
        if b[j]=="#": q.put([i,j,0])
#print(A)
while not q.empty():
    a,b,c = q.get()
    for x,y in [(1,0),(0,1),(-1,0),(0,-1)]:
        if 0<=b+y<h and 0<=a+x<w and A[b+y][a+x] == ".":
            #print(b+y,a+x)
            q.put([b+y,a+x,c+1])
            l = list(A[b+y])
            l[a+x] = "#"
            A[b+y] = "".join(l)
    if q.empty():
        print(c)
        break
#print(A)




### FIXED CODE ###

import numpy as np
def main():
    h,w = map(int, input().split())
    mat = []
    for i in range(h):
        b = input()
        mat.append([0 if j=="#" else h+w for j in b])
    arr = np.array(mat)

    for i in range(w-1):
        arr[:,i+1] = np.minimum(arr[:,i]+1,arr[:,i+1])
        #print(arr)

    for i in range(w-1,0,-1):
        arr[:,i-1] = np.minimum(arr[:,i]+1,arr[:,i-1])
        #print(arr)

    for i in range(h-1):
        arr[i+1,:] = np.minimum(arr[i,:]+1,arr[i+1,:])
        #print(arr)

    for i in range(h-1,0,-1):
        arr[i-1,:] = np.minimum(arr[i,:]+1, arr[i-1,:])
        #print(arr)
    print(np.max(arr))


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

from collections import defaultdict


class UnionFind:
    def __init__(self, n=0):
        self.d = {i: -1 for i in range(n)}

    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if (x == y):
            return False
        if (self.d[x] > self.d[y]):
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.d[self.find(x)]


N, M, K = map(int, input().split(' '))
deg = defaultdict(int)
to = defaultdict(list)
uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.unite(a, b)

for _ in range(K):
    c, d = map(int, input().split(' '))
    c -= 1
    d -= 1
    to[c].append(d)
    to[d].append(c)

for i in range(N):
    ans = uf.size(i) - 1 - deg[i]
    for u in to[i]:
        if uf.same(i, u):
            ans -= 1
    print(ans, end=' ' if i != (N - 1) else '\n')


### FIXED CODE ###

from collections import defaultdict


class UnionFind:
    def __init__(self, n=0):
        self.d = {i: -1 for i in range(n)}

    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if (x == y):
            return False
        if (self.d[x] > self.d[y]):
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.d[self.find(x)]


N, M, K = map(int, input().split(' '))
deg = defaultdict(int)
to = defaultdict(list)
uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.unite(a, b)

for _ in range(K):
    c, d = map(int, input().split(' '))
    c -= 1
    d -= 1
    to[c].append(d)
    to[d].append(c)

for i in range(N):
    ans = uf.size(i) - 1 - deg[i]
    for u in to[i]:
        if uf.same(i, u):
            ans -= 1
    print(ans, end=' ' if i != (N - 1) else '\n')
### BUGGY CODE ###

q = int(input())
for _ in range(q):
    x = input()
    y = input()
    m = len(x)
    n = len(y)
    c = [0] * (n + 1)
    for i in range(m):
        tmp = x[i]
        c_ = c[:]
        for j in range(n):
            if tmp == y[j]:
                c[j + 1] = c_[j] + 1
            elif c[j + 1] < c[j]:
                c[j + 1] = c[j]
    print(c[-1])


### FIXED CODE ###

def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [0] * (n + 1)
    for i in range(m):
        tmp = x[i]
        c_ = c[:]
        for j in range(n):
            if tmp == y[j]:
                c[j + 1] = c_[j] + 1
            elif c[j + 1] < c[j]:
                c[j + 1] = c[j]
    return c[-1]


q = int(input())
ans = []
for _ in range(q):
    x = input()
    y = input()
    ans.append(lcs(x, y))

print(*ans, sep="\n")
### BUGGY CODE ###

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

dp = [[[-1]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 0

def dfs(i, j, k, n):
    if dp[i][j][k] != -1:
        return dp[i][j][k]
    res = 1
    if k > 0:
        res += (k/n) * dfs(i, j, k-1, n)
    if j > 0:
        res += (j/n) * dfs(i, j-1, k+1, n)
    if i > 0:
        res += (i/n) * dfs(i-1, j+1, k, n)
    dp[i][j][k] = (n/(i+k+j)) * res
    return dp[i][j][k]

cnt1 = a.count(1)
cnt2 = a.count(2)
cnt3 = a.count(3)

dfs(cnt3, cnt2, cnt1, n)
print(dp[cnt3][cnt2][cnt1])

### FIXED CODE ###

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

dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 0

cnt1 = a.count(1)
cnt2 = a.count(2)
cnt3 = a.count(3)

for i in range(cnt3 + 1):
    for j in range(cnt3 + cnt2 + 1 - i):
        for k in range(cnt3 + cnt2 + cnt1 + 1 - i - j):
            if i + j + k == 0:
                continue
            res = 1
            if k > 0:
                res += (k/n) * dp[i][j][k-1]
            if j > 0:
                res += (j/n) * dp[i][j-1][k+1]
            if i > 0:
                res += (i/n) * dp[i-1][j+1][k]
            dp[i][j][k] = (n/(i+k+j)) * res

print(dp[cnt3][cnt2][cnt1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
v = [[] for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].append(b)
  v[b].append(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  temp = v[p]
  for i in temp:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def input():
  return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
v = [[] for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].append(b)
  v[b].append(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  for i in v[p]:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])
### BUGGY CODE ###

from collections import deque
x,y,z,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
b = sorted(list(map(int,input().split())),reverse=True)
c = sorted(list(map(int,input().split())),reverse=True)
ans = []
for i in range(x):
    for j in range(y):
        for m in range(z):
            if (i+1)*(j+1)*(m+1) <= k:
                ans.append(a[i]+b[j]+c[m])

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

### FIXED CODE ###

from collections import deque
x,y,z,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
b = sorted(list(map(int,input().split())),reverse=True)
c = sorted(list(map(int,input().split())),reverse=True)
ans = []
for i in range(x):
    for j in range(y):
        for m in range(z):
            if (i+1)*(j+1)*(m+1) <= k:
                ans.append(a[i]+b[j]+c[m])
            else:
                break

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

n,m = map(int, input().split())
keys = []
for i in range(m):
  l,r = map(int, input().split())
  keys.append(set(range(l,r+1)))
print(len(set.intersection(*keys)))

### FIXED CODE ###

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

x,k,d=map(int, input().split()) 
tmp = k

ans = abs(x)%d
k = k - int(abs(x)/d)

if k < 0:
    ans = x
    k = tmp

for i in range(k):
    if abs(ans) <= d and (k-i)%2 == 0:
        print(abs(ans))
        exit()
    elif ans >= 0:
        ans = ans - d
    elif ans < 0:
        ans = ans + d

print(abs(ans))


### FIXED CODE ###

x,k,d=map(int, input().split()) 
tmp = k

ans = abs(x)%d
k = k - int(abs(x)/d)

if k < 0:
    ans = abs(x)
    ans = ans - (tmp * d)
    print(ans)
    exit()

for i in range(k):
    if abs(ans) <= d and (k-i)%2 == 0:
        print(abs(ans))
        exit()
    elif ans >= 0:
        ans = ans - d
    elif ans < 0:
        ans = ans + d

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

N = int(input())
result = 1
TEISU = 10 **9 + 7
for i in range(N):
    result *= (i + 1)
if result > TEISU:
    print(result % TEISU)
else:
    print(result)


### FIXED CODE ###

N = int(input())
result = 1
TEISU = 10 **9 + 7

for i in range(N):
    result = (i + 1) * result % TEISU
print(result)
### BUGGY CODE ###

def kosu(kitei, aaa):
    ret = 0
    n=len(kitei)
    for i in range(n):
        if kitei[i]:
            ret += 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]
    
    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 ret==ret2:
        return 1
    else:
        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)>0:
                pass
            else:
                kitei.append(now)
        else:
            if kosu(kitei, now)>0:
                pass
            else:
                answer=1
        #print(kitei)
    return answer


t=int(input())
for i in range(t):
    n=int(input())
    alist = list(map(int, input().split()))
    s=input()
    print(solve(n, alist, s))

### FIXED CODE ###

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)
        else:
            if kosu(kitei, now, 0)>0:
                pass
            else:
                answer=1
        #print(kitei)
    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))