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

from collections import defaultdict
from itertools import combinations
import sys
input = sys.stdin.readline

n = int(input())
s = [input().split()[0] for _ in range(n)]
cnt = defaultdict(int)
for i in range(n):
    cnt["".join(sorted(s[i]))] += 1
result = 0
for c in cnt:
    for i in combinations([""] * cnt[c], 2):
        result += 1
print(result)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = ["".join(sorted(input().split()[0])) for _ in range(n)]
cnt = {}
result = 0
for si in s:
    if si in cnt:
        result += cnt[si]
        cnt[si] += 1
    else:
        cnt[si] = 1
print(result)
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def calc_combination(n):
    count = 0
    for a in xrange((n if n < 1000 else 1000) + 1):
        e1 = n-a-1001 if n-a-1001 >= 0 else -1
        for nab in xrange(n-a, e1, -1):
            ran = ((nab if nab < 1000 else 1000) -
                   ((nab-1001) if nab > 1000 else -1))
            if ran >= 0:
                count += ran
    return count


def main():
    ans = [0] * 4001
    for line in stdin:
        n = int(line)

        if not ans[n]:
            count = calc_combination(n)
            ans[n] = count
            ans[4000-n] = count
        print(ans[n])
    exit()


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def make_combination_list():
    cmb = [0] * 4001
    count = minus = n = s = 0

    for i in range(1001):
        count += (i+1) * (i+2) // 2
        cmb[i] = cmb[4000-i] = count

    for i in range(1001, 2001):
        count += (i+1) * (i+2) // 2
        n += 1
        s += n
        minus += 4 * s
        cmb[i] = cmb[4000-i] = count - minus

    return cmb


def main():
    ans = make_combination_list()
    for line in stdin:
        print(ans[int(line)])


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

from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
B = [i for i in range(N)]
MOD = 10 ** 9 + 7
def lcm(a,b):
    return a * b // gcd(a, b)
h = reduce(lcm, A)

for i in range(N):
    B[i] = (h // A[i] % MOD)

print(sum(B) % MOD)


### FIXED CODE ###

from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

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

def modpow(a, n, mod): # a^n mod
    result = 1
    while n > 0:
        if n & 1: result = result * a % mod
        a = a * a % mod
        n >>= 1
    return result

h = reduce(lcm, A)
B = [h * modpow(A[i], MOD-2, MOD) for i in range(N)]
print(sum(B) % MOD)
### BUGGY CODE ###

a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]
d=[list(map(int,input().split())) for i in range(b)]
e=[[]for i in range(a)]

for i in c:
  e[i[0]-1].append(i[1]-1)
  e[i[1]-1].append(i[0]-1)


g=[[]for i in range(a)]
n=0
f=[0 for _ in range(a)]
ans=[0 for _ in range(a)]
for i in d:
  ans[i[0]-1]=ans[i[0]-1]+i[1]
i=0
h=[]
while n<a:
  n+=1
  m=float("inf")
  for j,k in enumerate(e[i]):
    if f[i]==k:
      m=j
    else:
      f[k]=i
  if m!=float("inf"):
    e[i].pop(m)
  h=h+e[i]
  for j in e[i]:
    ans[j]+=ans[i]
  if len(h)!=0:
    i=h.pop()



  

  
print(" ".join(map(str,ans)))
    
  

  
  

### FIXED CODE ###

from collections import deque
a,b=map(int,input().split())
e=[[]for i in range(a)]

for i in range(a-1):
  c1,c2=map(int,input().split())
  e[c1-1].append(c2-1)
  e[c2-1].append(c1-1)

g=[[]for i in range(a)]
f=deque()
f.append((0,-1))
ans=[0 for _ in range(a)]
for i in range(b):
  ten,p=map(int,input().split())
  ans[ten-1]+=p
i=0
while len(f)!=0:
  i,fr=f.popleft()
  for j in e[i]:
    if j==fr:
      continue
    else:
      ans[j]+=ans[i]
      f.append([j,i]) 
print(*ans)
### BUGGY CODE ###


n = int(input())
ab = str(input())
a = list(ab)
b = list(range(0, len(a)+1))

e = list(zip(a,b))
visited = []
count = [0]
while len(e) >0:
    x,y = e.pop()
    lenx = len(x)
    z = ab[y+lenx:].find(x)
    if z == -1:
        visited.append((x,y))
    else:
        f = y+z+1
        g = (x, y)
        count.append(lenx)
        visited.append(g)

        h = (ab[y:y+lenx+1], y)
        e.insert(0, h)

print(count[-1])

### FIXED CODE ###


n = int(input())
ab = str(input())

ans = set([0])
lenab = len(ab)

for h in range(lenab):
    abc = ab[h:]
    lenabc = len(abc)
    i = 1; j = 0
    A = [0]*lenabc
    A[0] = lenabc
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < i:
            j += 1
        if j == 0:
            i += 1
        else:
            A[i] = j
            ans.add(j)
            k = 1
            while lenabc - i > k < j - A[k] and j < i - k :
                A[i + k] = A[k]
                k += 1
            i += k;
            j -= k

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

n,q=map(int,input().split())
s=input()
i=0
bb=[]
while True:
    b=s.find('AC', i)
    if b<0:
        break
    bb.append(b)
    i=b+1
for _ in range(q):
    l,r=map(int,input().split())
    print(sum(1 for b in bb if l-1<=b<=r-2))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
i=0
bb=[]
c=0
while True:
    b=s.find('AC', i)
    if b<0:
        bb.extend([c]*(len(s)-i))
        break
    bb.extend([c]*(b-i+1))
    i=b+1
    c+=1
for _ in range(q):
    l,r=map(int,input().split())
    print(bb[r-1]-bb[l-1])
### BUGGY CODE ###

def division(x,y):
    if y == 0:
        return x
    return  division(y, x%y)

def checker(x):
    for i in range(2,x//2+1):
        v = division(x,i)
        if v > 1 :
            return False
    return True

cnt=0
q=int(input())
for i in range(q):
    o=checker(int(input()))
    if o:
        cnt+=1
print(cnt)

### FIXED CODE ###

def checker(x):
    if x == 2:
        return True
    if x < 2 or x % 2 == 0 :
        return False
    for i in range(2,int(x**0.5)+1):
        if x % i == 0 :
            return False
    return True

cnt=0
q=int(input())
for _ in range(q):
    v=int(input())
    if checker(v):
        cnt += 1
print(cnt)
### BUGGY CODE ###

n,k = map(int, input().split())
p = [int(x) for x in input().split()]

max = -1
ans=0


for i in range(0,n-k+2):
    buf = p[i:i+k]
    tmp = sum(buf)
    if tmp > max:
        max = tmp
        li = p[i:i+k]

for j in range(len(li)):
    s_buf = 0
    for l in range(1,li[j]+1):
        s_buf+=l
    ans += s_buf/li[j]
    s_buf=0

print(ans)


### FIXED CODE ###

n,k = map(int, input().split())
p = [int(x) for x in input().split()]

li = []
count=0
ans = 0

for i in range(len(p)):
    p[i] += 1
    li.append(p[i])
    if len(li) < k:
        continue
    elif len(li) == k:
        max = sum(li)
        buf = max
    elif len(li) > k:
        tmp = buf - li[count] + li[-1]
        buf = tmp
        if tmp >= max:
            max = tmp
        count+=1

print(max/2)
### BUGGY CODE ###

import math
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]
primes = primes(10**5)
dp = [0]*(10**5+1)
cnt = 0
for i in range(1, 10**5+1, 2):
    if i in primes:
        if (i+1)//2 in primes:
            cnt += 1
    dp[i] = cnt

    
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(dp[r]-dp[l-2])

### FIXED CODE ###

import math
def primes(n):
    a = list(range(2, n+1))
    primes = [2]
    for i in a:
        flag = True
        m = math.sqrt(i)
        for j in primes:
            if j > m:
                break
            else:
                if i % j == 0:
                    flag = False
                    break
        if flag:
            primes.append(i)
    return primes
primes = primes(10**5)
anss = []
for p in primes:
    if (p+1)//2 in primes:
        anss.append(p)
dp = [0]*(10**5+1)
cnt = 0
for i in range(1, 10**5+1, 2):
    if i in anss:
        cnt += 1
    dp[i] = cnt

    
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(dp[r]-dp[l-2])
### BUGGY CODE ###


L,R=map(int,input().split())
M=2019
import sys
for i in range(L,R):
    for j in range(i+1,R+1) :
        if (i*j)%2019 < M :
            M = (i*j)%2019
    if M == 0:
       break
print (M)

### FIXED CODE ###

L,R=map(int,input().split())
M=2019
import sys
for i in range(L,R):
    for j in range(i+1,R+1) :
        if (i*j)%2019 < M :
            M = (i*j)%2019
            if M == 0:
                print(M)
                sys.exit()
print (M)
### BUGGY CODE ###

n = int(input())
x = input()

ppc = {}
ppc[0] = 0
def popcount(n):    
  if n in ppc:
    return ppc[n]  
  if n == 0:
    return 0
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

for i in range(n):
  popcount(i)

for i in range(2*10**5+1):
  popcount(i)
  
bit = int('0b'+x,0)
bn = x.count('1')
for i in range(n):
  if x[i] == '1':   
    bt = bn-1
    if bt == 0:
      print(0)
      continue
  else:
    bt = bn+1  
  tmp = bit ^ (1<<(n-i-1))
  print(ppc[tmp%bt]+1)
  

### FIXED CODE ###

n = int(input())
X = input()

def goes_to_zero(n):
  cnt = 0
  while(n > 0):
    n %= bin(n).count('1')
    cnt += 1
  return cnt
  
c1 = X.count('1')
xint = int(X,2)
xtp = xint % (c1 + 1)
if (c1 - 1) == 0:  
  xtm = 0
else:
  xtm = xint % (c1 - 1)
  
for i in range(n)  :
  if X[i] == '0':
    print(goes_to_zero( (xtp + pow(2,n-1-i,(c1+1))) % (c1+1) ) + 1)
  else:
    if (c1-1) == 0:
      print(0)
    else:
      print(goes_to_zero( (xtm - pow(2,n-1-i,(c1-1)) ) % (c1-1) ) +1)
### BUGGY CODE ###

def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(k,n):
        before = 1
        for j in A[i-k:i]:
            before *= j
        if before < before/A[i-k]*A[i]:
            print("Yes")
        else:
            print("No")
resolve()

### FIXED CODE ###

def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(k, n):
        if A[i] > A[i-k]:
            print("Yes")
        else:
            print("No")
resolve()
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,k = inpl()
a = inpl()
a.sort()
res = 0
for i in range(n-k+1):
    if i == 0:
        c = 1
    else:
        c *= i+k-1
        c //= i
    # print(c)
    res += c*(a[i+k-1]-a[n-k-i])
    res %= mod
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv
comb = Combination(100010)
n,k = inpl()
a = inpl()
a.sort()
res = 0
for i in range(n-k+1):
    cc = comb(n-i-1,k-1)
    res += cc*(-a[i]+a[n-i-1])
    res %= mod
print(res)
### BUGGY CODE ###

n=int(input())
a=[int(input())for _ in range(n)]
maxmax=max(a)
for i in range(n):
  if a[i]==maxmax:
    print(sorted(a)[-2])
  else:
    print(maxmax)


### FIXED CODE ###

n=int(input())
a=[int(input())for _ in range(n)]
b=sorted(a)

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

import bisect
n,m=map(int,input().split())
d={i+1:[[],[]] for i in range(n)}
for i in range(m):
     p,y=map(int,input().split())
     idx=bisect.bisect_left(d[p][0],y)
     d[p][0].insert(idx,y)
     d[p][1].insert(idx,i)
tmp=[]
tmp2=[]
for k in d.keys():
     for i in range(len(d[k][0])):
          num=str(k).zfill(6)+str(i+1).zfill(6)
          idx=bisect.bisect_left(tmp,d[k][1][i])
          tmp.insert(idx,d[k][1][i])
          tmp2.insert(idx,num)
for x in tmp2:
     print(x)

### FIXED CODE ###

import bisect
n,m=map(int,input().split())
d=[]
for i in range(m):
     p,y=map(int,input().split())
     d.append([p,y,i])
d=sorted(d,key=lambda x:(x[0],x[1]))
tmp2=[0 for i in range(m)]
p_=0
cnt=0
for x in d:
     p,y,i=x
     if p_!=p:
          p_=p
          cnt=0
     cnt+=1
     tmp2[i]=str(p).zfill(6)+str(cnt).zfill(6)
for x in tmp2:
     print(x)
### BUGGY CODE ###

n, m = map(int, input().split())

a, b = [0] * m, [0] * m
for i in range(m):
    a[i], b[i] = map(int, input().split())

for i in range(m):
    if a[i] == 1:
        for j in range(m):
            if b[i] == a[j] and b[j] == n:
                print("POSSIBLE")
                exit()
    
print("IMPOSSIBLE")


### FIXED CODE ###

n, m = map(int, input().split())

a, b = [0] * m, [0] * m
root_i = [False] * n
root_n = [False] * n
for i in range(m):
    a[i], b[i] = map(int, input().split())

for i in range(m):
    if a[i] == 1:
        root_i[b[i]] = True
    elif b[i] == n:
        root_n[a[i]] = True

for i in range(n):
    if root_i[i] == True and root_n[i] == True:
        print("POSSIBLE")
        exit()
    
print("IMPOSSIBLE")
### BUGGY CODE ###

def solve():
    from collections import defaultdict, namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'time type x_coordinate')

    inf = 1 << 31

    n, q = map(int, input().split())

    e = []  # 通行止めと解除にクエリ分割
    for _ in range(n):
        s, t, x = map(int, input().split())
        # 区間[s, t)に通行止め
        e.append(Event(t - x, 0, x))  # 通行止め解除/0にすることで、解除と開始が同時刻の場合、先に解除される
        e.append(Event(s - x, 1, x))  # 通行止め開始/1にすることで、同上

    for _ in range(q):
        d = int(input())
        e.append(Event(d, 2, -1))  # 求値クエリ/2にすることで、通行止めの設定解除の反映後に到着する

    e.sort(key=attrgetter('time', 'type'))

    stop_cnt = defaultdict(int)
    stop_cnt[inf] = 1
    stop_set = {inf}
    curr = inf

    for evt in e:
        if evt.type == 0:
            stop_cnt[evt.x_coordinate] -= 1
            if not stop_cnt[evt.x_coordinate]:
                stop_set.discard(evt.x_coordinate)
                if curr == evt.x_coordinate:
                    curr = min(stop_set)
        elif evt.type == 1:
            stop_cnt[evt.x_coordinate] += 1
            if stop_cnt[evt.x_coordinate] == 1:
                stop_set.add(evt.x_coordinate)
            if evt.x_coordinate < curr:
                curr = evt.x_coordinate
        else:
            if curr == inf:
                print(-1)
            else:
                print(curr)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')
### BUGGY CODE ###

n = int(input())
a=list(map(int,input().split()))
a.sort()
dp = [True]*(a[n-1]+1)
for val in a:
    temp=2
    while val*temp<=a[n-1]:
        dp[val*temp]=False
        temp+=1
ans = 0
for val in a:
    if dp[val] and a.count(val)==1:
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
dp=[True]*a[-1]
def hantei(i):
    ans = True
    if i!=n-1:
        if a[i]==a[i+1]: ans = False
    if i!=0:
        if a[i]==a[i-1]: ans=False
    return ans
for val in set(a):
    for i in range(2*val,a[-1]+1,val): dp[i-1]=False
ans=0
for i in range(n):
    if dp[a[i]-1] and hantei(i)==1: ans+=1
print(ans)
### BUGGY CODE ###

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

from decimal import *
import numpy as np


getcontext().prec = 2

L = int(input())
L = Decimal(L)

x=y=z=0
x = Decimal(x)
y = Decimal(y)
z = Decimal(z)


p = 0.01
p = Decimal(p)

maxV = 0

for x in np.arange(p,L+1,p):
    for y in np.arange(p,L+1,p):
        z = L-(x+y)

        V = x*y*z
    
        if maxV < V:
            maxV = V


print(maxV)

### FIXED CODE ###

L = int(input())

x=y=z=0

x=y=z=L/3

V = x*y*z




print(V)
### BUGGY CODE ###

p = int(input())
A = [int(x) for x in input().split()]

def swap(a, b):
        return (b, a)

def modinv(a, m):
        b = m
        u = 1
        v = 0
        while b:
                t = a // b
                a -= t * b
                a, b = swap(a, b)
                u -= t * v
                u, v = swap(u, v)
        u %= m
        if u < 0:
                u += m
        return u

# p-1C0, p-1C1, ..., p-1Cp-1
binomial = []
for i in range(p):
    num = 1
    denom = 1
    for j in range(1, i+1):
        num *= (p-j)
        denom *= j
        num %= p
        denom %= p
    binomial.append(num * modinv(denom, p) % p)

ret = [0] * p
for i in range(p):
    if A[i] == 0:
        continue

    ret[0] += 1
    for j in range(p):
        ret[j] -= binomial[j] * (-i) ** (p-1-j)
        ret[j] %= p

ans = ''
for i in range(p):
    ans += str(ret[i]%p) + ' '

print(ans)
        


### FIXED CODE ###

p = int(input())
A = [int(x) for x in input().split()]

def modinv(a, m):
        b = m
        u = 1
        v = 0
        while b:
                t = a // b
                a -= t * b
                a, b = b, a
                u -= t * v
                u, v = v, u
        u %= m
        if u < 0:
                u += m
        return u
        
inv_factorial = [1]
prod = 1
for i in range(1, p):
    prod *= i
    prod %= p
    inv_factorial.append(modinv(prod, p))

#p-1C0, p-1C1, ..., p-1Cp-1
comb = []
for i in range(p):
    l = i
    r = p-1-i
    comb.append(-1 * inv_factorial[l] * inv_factorial[r] % p)

ret = [0] * p
for i in range(p):
    if A[i] == 0:
        continue

    ret[0] += 1
    temp = 1
    for j in range(p):
        ind = p-j-1
        if j > 0:
            temp *= (-i)
            temp %= p
        ret[ind] -= comb[ind] * temp
        ret[ind] %= p

print(*ret)
### BUGGY CODE ###

N, S = map(int, input().split())
As = list(map(int, input().split()))
mod = 998244353
dp = [[2**i%mod]+[0]*(S) for i in range(N+1)]

for i in range(1, N+1):
    a = As[i-1]
    for s in range(1, S+1):
        dp[i][s] += max(0, dp[i-1][s])*2
        if s-a>=0:
            dp[i][s] += dp[i-1][s-a]
        dp[i][s] %= mod
print(dp[-1][-1]%mod)

### FIXED CODE ###

N, S = map(int, input().split())
As = list(map(int, input().split()))
mod = 998244353
dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    a = As[i-1]
    for s in range(S+1):
        if s-a>=0:
            dp[i][s] += dp[i-1][s-a] + dp[i-1][s]*2
        else:
            dp[i][s] += dp[i-1][s]*2
        dp[i][s] %= mod
print(dp[-1][-1]%mod)
### BUGGY CODE ###

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])
	#exit(0)

def sol(N,vA,S):
	sZ = {0,}
	for a,c in zip(vA[::-1],S[::-1]):
		if c=="0":
			sZ |= {a^z for z in sZ}
		elif a not in sZ:
			sZ = set({})
		else:
			pass	# sZ = sZ
		#print(sZ)##
	
	res = 1
	if sZ:
		res = 0
	
	#print(sZ)###
	print(res)


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

def ran():
	#N = 200
	N=8
	vRan = [random.randint(1,10) for _ in "*"*N]
	S = "".join(str(random.randint(0,1)) for _ in "*"*N)
	#print(max(vRan))#
	print(vRan,S)
	sol(N, vRan, S)
	
if __name__ == "__main__":
	main()
	#ran()


### FIXED CODE ###

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])
	#exit(0)

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 not N: print(z,v)##
		if c=="0":
			sZ |= {v,}
		elif v not in sZ:
			sZ = set({})
			break
		#else:
		#	pass	# sZ = sZ
		#if not N: print(sZ)##
	
	res = 1
	if sZ:
		res = 0
	
	#print(sZ)###
	print(res)


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

def ran():
	N = 200
	#N=6
	vRan = [random.randint(1,10) for _ in "*"*N]
	S = "".join(str(random.randint(0,1)) for _ in "*"*N)
	#print(max(vRan))#
	#vRan = [5, 7, 7, 3, 1, 7]###
	#S = "111000"###
	print(vRan,S)
	sol(N=0, vA=vRan, S=S)
	exit(0)
	
if __name__ == "__main__":
	#ran()
	main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

n, m = map(int, input().split())

root = [-1] * n


def r(x):
    if root[x] < 0:
        return x

    return r(root[x])


def unite(x, y):
    x = r(x)
    y = r(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x


def size(x):
    return -1 * root[r(x)]


for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)

ans = 0
for i in range(n):
    ans = max(ans, size(i))

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

n, m = map(int, input().split())

root = [-1] * n


def r(x):
    if root[x] < 0:
        return x
    else:
        root[x] = r(root[x])
        return root[x]


def unite(x, y):
    x = r(x)
    y = r(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x


def size(x):
    return -1 * root[r(x)]


for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)

ans = 0
for i in range(n):
    ans = max(ans, size(i))

print(ans)