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

import sys

s = input()
t = input()

t_set = set(t)

if len(t_set -set(s)) != 0:
    print(-1)
    sys.exit()

s_len = len(s)
def index_list(char):
    word = s
    ret = list()
    sum = 0
    try:
        while True:
            index = word.index(char)+ 1        
            sum+=index
            ret.append(sum)
            word = word[index:]
    except:
        if sum == 0:
            ret.append(-1)
    return ret

alpha_dict = dict()
for char in t_set:
    alpha_dict[char] = index_list(char)

index_old = 0
n_s = 0
for char in t:
    index = alpha_dict[char]
    
    if index[0] == -1:
        index_old = -1
        break
    
    flg = True
    for i in index:
        if i>index_old:
            index_old = i
            flg =False
            break
    if flg:
        index_old = index[0]
        n_s += 1

if index_old == -1:
    print(-1)
else:
    print(n_s*s_len + index_old)
        
    
            

    
    


    
    

### FIXED CODE ###

import sys
s = input()
t = input()
tset = set(t)
slen = len(s)
if len(tset - set(s)) != 0:
    print(-1)
    sys.exit()
s2t = [i - ord('a') for i in (s + s).encode('ascii')]
lut = [[-1 for _ in range(slen)] for _ in range(26)]
for c in tset:
  b = ord(c) - ord('a')
  j = 0
  for i in range(slen * 2 - 1, -1, -1):
    if s2t[i] == b:
      j = 0
    else:
      j += 1
    if i < slen:
      lut[b][i] = j
p = 0
for c in t:
  b = ord(c) - ord('a')
  p += lut[b][p % slen] + 1
print(p)
### BUGGY CODE ###

def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    M = [0 for _ in range(100000)]
    for i, row in enumerate(A):
        for j, v in enumerate(row):
            M[v] = (i, j)
    Q = int(input())
    P = []
    ans = []
    for _ in range(Q):
        L, R = map(int, input().split())
        if L == R:
            ans.append(0)
            continue
        while True:
            P.append(M[L])
            if L == R:
                break
            L += D
        m = 0
        for i in range(len(P) - 1):
            m += abs(P[i][0] - P[i + 1][0]) + abs(P[i][1] - P[i + 1][1])
        ans.append(m)
    for a in ans:
        print(a)


main()


### FIXED CODE ###

def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    Q = int(input())
    ans = []

    x = [0 for _ in range(90001)]
    y = [0 for _ in range(90001)]
    dp = [0 for _ in range(90001)]

    for i, row in enumerate(A):
        for j, a in enumerate(row):
            x[a] = j
            y[a] = i
    for i in range(D + 1, H * W + 1):
        dp[i] = dp[i - D] + abs(x[i] - x[i - D]) + abs(y[i] - y[i - D])

    for _ in range(Q):
        L, R = map(int, input().split())
        ans.append(dp[R] - dp[L])
    for a in ans:
        print(a)


main()
### BUGGY CODE ###

from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
BC = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]
BC.sort(key=lambda x: (x[1]), reverse=True)

for B, C in BC: # O(10^5)
    A.sort()
    if A[0] > C:
        break
    for i in range(B):
        if A[i] < C:
            A[i] = C
        else:
            print(sum(A))
            exit()

print(sum(A))

### FIXED CODE ###

from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
BC = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]
A.sort()
BC.sort(key=lambda x: (x[1]), reverse=True)

i = 0
A_len = len(A)

for B, C in BC: # O(10^5)
    for _ in range(B):
        if A[i] < C:
            A[i] = C
            i += 1
            if i > A_len - 1:
                print(sum(A))
                exit()
        else:
            print(sum(A))
            exit()

print(sum(A))
### BUGGY CODE ###

n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [0]*(n+1)
memo[0]=1
su = 0
if 1 in l:
  memo[1]=0
else:
  memo[1]=1

for i in range(2,n+1):
  if i in l:
    continue
  else:
    memo[i]=memo[i-1]+memo[i-2]
print(memo[-1]%q)

### FIXED CODE ###

n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [-1]*(n+1)
memo[0]=1
su = 0
if 1 in l:
  memo[1]=0
else:
  memo[1]=1
for j in l:
  memo[j]=0
  
for i in range(2,n+1):
  if memo[i]==0:
    continue
  else:
    memo[i]=((memo[i-1]%q)+(memo[i-2]%q))%q
print(memo[-1]%q)
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
q=int(input())
bc=[]

for i in range (q):
    bc.append(list(map(int, input().split())))
num=[0]*(10**5+1)
for i in range(n):
    x=a[i]
    num[x]+=1


for k in range (q):
    b=bc[k][0]
    c=bc[k][1]
    num[c]+=num[b]
    num[b]=0
    kk=0
    for l in range(10**5+1):
        kk+=l*num[l]
    print(kk)

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
q=int(input())
bc=[]

for i in range (q):
    bc.append(list(map(int, input().split())))
num=[0]*(10**5+1)
for i in range(n):
    x=a[i]
    num[x]+=1

kk=0
for l in range(10**5+1):
    kk+=l*num[l]

for k in range (q):
    b=bc[k][0]
    c=bc[k][1]
    kk+=c*num[b]-b*num[b]
    num[c]+=num[b]
    num[b]=0
    print(kk)
### BUGGY CODE ###

[n,k] = [int(i) for i in input().split()]
p = [(int(i)+1)/2 for i in input().split()]
ans = 0
for i in range(n-k+1):
	ans = max(ans,sum(p[i:i+k]))
print(ans)


### FIXED CODE ###

[n,k] = [int(i) for i in input().split()]
p = [(int(i)+1)/2 for i in input().split()]
sm_l = [0]
#sm_r = [0]
for i in range(n):
	sm_l.append(sm_l[-1] + p[i])
	#sm_r.append(sm_r[-1] + p[-i-1])
ans = 0
for i in range(n-k+1):
	ans = max(ans,sm_l[i+k]-sm_l[i])
print(ans)
### BUGGY CODE ###

def solve(H, M, W, bombs):
    count_h = [0 for _ in range(H)]
    count_w = [0 for _ in range(W)]
    for b in bombs:
        count_h[b[0]] += 1
        count_w[b[1]] += 1
    max_h = max(count_h)
    max_w = max(count_w)
    points_h = [i for i, c in enumerate(count_h) if c == max_h]
    points_w = [i for i, c in enumerate(count_w) if c == max_w]
    ans = max_h + max_w
    if _find_cross_bomb(points_h, points_w, bombs):
        ans -= 1
    print(ans)


def _find_cross_bomb(points_h, points_w, bombs):
    c = 0
    for b in bombs:
        if (b[0]) in points_h:
            if (b[1]) in points_w:
                c += 1
    return c == len(points_h) * len(points_w)


if __name__ == "__main__":
    H, W, M = map(int, input().split())
    bombs = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]
    solve(H, M, W, bombs)


### FIXED CODE ###

import sys


def solve():
    readline = sys.stdin.readline
    H, W, M = map(int, readline().split())
    h = [0] * H
    w = [0] * W
    b = set()
    for _ in range(M):
        y, x = map(int, readline().split())
        x -= 1
        y -= 1
        h[y] += 1
        w[x] += 1
        b.add(y * W + x)
    h = sorted(zip(h, range(H)), reverse=True)
    ans = 0
    for i in range(W):
        x = w[i]
        for y, j in h:
            if x + y > ans:
                if j * W + i in b:
                    ans = x + y - 1
                else:
                    ans = x + y
                    break
            else:
                break
    print(ans)


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

import itertools
n = int(input())
a = list(map(int, input().split()))
ok = False
for v in itertools.permutations(a):
    v = v+v[:2]
    for i in range(n):
        if v[i+1] != int(bin(v[i] ^ v[i+2])[2:], 2): break
        if i == n-1:
            if v[i+1] == int(bin(v[i] ^ v[i+2])[2:], 2):
                ok = True
    if ok: break
print("Yes" if ok else "No")

### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
c0 = a.count(0)

ans = "No"
if c0==n: ans = "Yes"
elif len(set(a)) == 2:
    c = a.count(a[-1])
    if c == (2*n)//3 and c0 == n//3: ans = "Yes"
elif len(set(a)) == 3:
    x,y,z = list(set(a))
    if a.count(x) == a.count(y) == a.count(z):
        if int(bin(x ^ y ^ z),2) == 0: ans = "Yes"
print(ans)
### BUGGY CODE ###

N = int(input())
a = []
for _ in range(N):
    a.append(int(input()))

x = 1
count = 0
while x != 2:
    x = a[x-1]
    count += 1
    if x == 1:
        print(-1)
        break
else:
    print(count)

### FIXED CODE ###

N = int(input())
a = []
for _ in range(N):
    a.append(int(input()))

x = 1
s = {1}
count = 0
while x != 2:
    x = a[x-1]
    count += 1
    if x in s:
        print(-1)
        break
    s.add(x)
else:
    print(count)
### BUGGY CODE ###

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

A3 = 0
for i in range(2, N):
    A3 ^= A[i]

ans = -1
for i in range(A[0]):
    if (A[0] - i) ^ (A[1] + i) == A3:
        ans = i
        break
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
P = 41

X = 0
for i in range(2, N):
    X ^= A[i]

S = A[0] + A[1]
A1 = A[0]

D, M = divmod(S - X, 2)
ans = -1
if M % 2 == 0 and D & X == 0 and D <= A1:
    Y = 0
    for p in range(P, -1, -1):
        if (X >> p) & 1 == 1:
            new_Y = Y ^ (1 << p)
            if D ^ new_Y <= A1:
                Y = new_Y

    ans = A1 - (D ^ Y)
    if ans == A1:
        ans = -1

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

N, A = map(int, input().split())
X = list(map(int, input().split()))

nega = []
posi = []
zero = 0
for x in X:
    if x < A: nega.append(A-x)
    elif A < x: posi.append(x-A)
    else: zero += 1

if len(nega) <= len(posi):
    arrf = sorted(nega)[::-1]
    arrg = sorted(posi)[::-1]
else:
    arrf = sorted(posi)[::-1]
    arrg = sorted(nega)[::-1]

from collections import defaultdict
from itertools import product
ans = 0
f = defaultdict(int)
g = defaultdict(int)
fmax = 0

for vr in product(range(2), repeat=len(arrf)):
    x = 0
    for i in range(len(vr)):
        x += vr[i] * arrf[i]
    if x == 0: continue
    f[x] += 1
    fmax = max(fmax, x)

for vr in product(range(2), repeat=len(arrg)):
    x = 0
    for j in range(len(vr)):
        x += vr[j] * arrg[j]
        if fmax < x: break
    if x == 0: continue
    g[x] += 1
    ans += f[x]

ans *= 2 ** zero
ans += 2 ** zero - 1
print(ans)

### FIXED CODE ###

def abc044_c():
    import numpy as np
    n, a = map(int, input().split())
    x = list(map(lambda x: int(x) - a, input().split()))  # 平均ターゲット値を引いておく
    x = np.array(x, dtype=np.int64)

    vrange = n * (a + np.max(x))  # 取りうる値の幅(片側), 広めにとってもかまわない
    dp = np.zeros((n+1, 2*vrange+1), dtype=np.int64)  # DPテーブル
    dp[0, vrange] = 1  # 0枚時点で何も選ばずに総和0(平均ターゲット)になる場合を初期値にセット

    for i in np.arange(n):
        # 1つ前のターンを引き継ぐ
        dp[i+1, :] += dp[i, :]
        if 0 < x[i]:
            # x[i]が正の値、1つ前のx[i]個ぶん左側をスライドして持ってくる
            dp[i+1, x[i]:] += dp[i, :-x[i]]
        elif x[i] < 0:
            # x[i]が負の値、1つ前のx[i]個ぶん右側をスライドして持ってくる
            dp[i+1, :x[i]] += dp[i, -x[i]:]
        else:
            # x[i]がゼロ
            dp[i+1, :] += dp[i, :]

    ans = dp[n, vrange] - 1  # 初期値(何も選ばない)の1通りを除く
    print(ans)

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

from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]

for d in A:
    A  = [x for x in A if (x == d or x % d != 0)]
each = Counter(A)
result = 0
for key in each:
    if each[key] == 1:
         result += 1
print(result)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]
maxA = max(A)
dp = {}
for i in range(1, maxA+1):
    dp[i] = True
for i in range(N):
    if dp[A[i]]:
        tmp = 2 * A[i]
        while maxA >= tmp:
            if dp[tmp]:
                dp[tmp] = False
            tmp += A[i]
counter = 0
t = Counter(A)
for i in range(N):
    if dp[A[i]] and t[A[i]] == 1:
        counter += 1
print(counter)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if str(i)[0] == str(j)[-1] and str(i)[-1] == str(j)[0]:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())

def count_ab(start, end):
    l = len(str(n))
    if start == 0:
        return 0
    if l == 1:
        if start == end:
            if n >= start:
                return 1
            else:
                return 0
        else:
            return 0
    else:
        if start == end:
            cnt = 1
        else:
            cnt = 0
        if int(str(n)[0]) > start:
            for i in range(1, l):
                cnt += 10 ** i // 10
        if int(str(n)[0]) == start:
            for i in range(1, l - 1):
                cnt += 10 ** i //10
            cnt += int(str(n)[1:]) // 10
            if int(str(n)[-1]) >= end:
                cnt += 1
        if int(str(n)[0]) < start:
            for i in range(1, l - 1):
                cnt += 10 ** i //10
        return cnt

ans = 0
for i in range(10):
    for j in range(10):
        A = count_ab(i, j)
        B = count_ab(j, i)
        ans += A * B

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

import sys
input = sys.stdin.readline
import numpy as np

H,W,D = map(int,input().split())
N = H*W

# 各数値の書かれている位置, 1-indexed
X = np.zeros(N+1,dtype=np.int64)
Y = np.zeros(N+1,dtype=np.int64)

for x in range(H):
  row = input()
  for y,n in enumerate(row.split()):
    X[int(n)] = x
    Y[int(n)] = y

#n%Dからnへ移動するために必要な魔力
MAGIC = np.zeros(N+1,dtype=np.int64)

for d in range(1,D+1):
  DX = np.abs(np.diff(X[d::D]))
  DY = np.abs(np.diff(Y[d::D]))
  MAGIC[d+D::D] = (DX + DY).cumsum()


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

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np

H,W,D = map(int,input().split())
N = H*W
ND = N//D

# 各数値の書かれている位置, 1-indexed
X = np.zeros((D,ND+1),dtype=np.int64)
Y = np.zeros((D,ND+1),dtype=np.int64)

for x in range(H):
  row = input()
  for y,n in enumerate(row.split()):
    n = int(n)
    q,r = n//D,n%D
    X[r,q] = x
    Y[r,q] = y

# 0D+d から nD+d への移動コスト
MAGIC = np.zeros_like(X)
MAGIC[:,1:] = (np.abs(np.diff(X,axis = 1)) + np.abs(np.diff(Y,axis = 1))).cumsum(axis = 1)

Q = int(input())
for _ in range(Q):
  l,r = map(int,input().split())
  d = l%D
  print(MAGIC[d,r//D] - MAGIC[d,l//D])
### BUGGY CODE ###

import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re

N=int(input())
C=input()

chk = N - 1
cnt = 0

for i in range(N):
    if C[i] == 'W':
        for x in reversed(range(0,chk+1)):
            if C[x] == 'R':
                chk = x
                break
        if chk <= i:
            break
        else:
            cnt = cnt + 1
            chk = chk - 1

print(cnt)


### FIXED CODE ###

import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re

def main_chk():
    N=int(input())
    C=input()

    chk = N - 1
    cnt = 0

    for i in range(N):
        if C[i] == 'W':
            p = chk
            chk = i
            for x in range(N-i):
                if C[p-x] == 'R':
                    chk = p - x
                    break
            if chk <= i:
                break
            else:
                cnt = cnt + 1
                chk = chk - 1
                if chk <= i + 1:
                    break

    print(cnt)

main_chk()
### BUGGY CODE ###

from functools import cmp_to_key
from heapq import heappush, heappop, heapify
n, m = map(int, input().split())
a = [int(e) for e in input().split()]
heapify(a)
bc = [[int(e) for e in input().split()] for _ in range(m)]
bc.sort(key = cmp_to_key(lambda x, y: x[1] - y[1]))
for i in range(m):
  b, c = bc[i]
  for j in range(b):
    t = heappop(a)
    if t < c:
      heappush(a, c)
    else:
      heappush(a, t)
      break
print(sum(a))


### FIXED CODE ###

from functools import cmp_to_key
n, m = map(int, input().split())
a = [int(e) for e in input().split()]
bc = [[int(e) for e in input().split()] for _ in range(m)]
bc.sort(key = cmp_to_key(lambda x, y: y[1] - x[1]))
t = 0
for v in bc:
  b, c = v
  t += b
  a.extend([c] * b)
  if t > n:
    break
a.sort(reverse = True)
print(sum(a[:n]))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split())) 
for i in range(1, N+1):
  print(A.count(i))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split())) 
d = {}
for i in range(1, N+1):
  d[i] = 0

for i in A:
  d[i] += 1

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

a, b = map(int, input().split())

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

n = gcd(a, b)

if n == 1:
    print(1)
    exit()

m = 2
ans = 1
while n > 1 and m <= n:
    if n % m == 0:
        ans += 1
        while n % m == 0:
            n //= m
    #print(n, m)
    m += 1

print(ans)


### FIXED CODE ###

a, b = map(int, input().split())

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

n = gcd(a, b)

if n == 1:
    print(1)
    exit()

m = 2
ans = 1
while m <= (n ** 0.5):
    if n % m == 0:
        ans += 1
        while n % m == 0:
            n //= m
    if n == 1:
        break
    m += 1

if n > 1:
    ans += 1

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

import sys
sys.setrecursionlimit(1000000)

N,M,Q = [int(x) for x in input().split()]
lr = [[int(x) for x in input().split()]for _ in range(M)]
pq = [[int(x) for x in input().split()]for _ in range(Q)]

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

for i in lr:
    for j in range(i[0]+1):
        dp[j][i[1]]+=1

for i in range(N,0,-1):
    for j in range(i,N+1):
        if(j!=i):
            dp[i][j] += dp[i][j-1]

for i in pq:
    print(dp[i[0]][i[1]])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N,M,Q = [int(x) for x in input().split()]
lr = [[int(x) for x in input().split()]for _ in range(M)]
pq = [[int(x) for x in input().split()]for _ in range(Q)]

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

for i in lr:
    dp[i[0]][i[1]]+=1

for j in range(N+1):
    for i in range(N-1,0,-1):
        dp[i][j] += dp[i+1][j]

for i in range(N,0,-1):
    for j in range(i,N+1):
        if(j!=i):
            dp[i][j] += dp[i][j-1]

for i in pq:
    print(dp[i[0]][i[1]])
### BUGGY CODE ###

import math
import itertools
K = int(input())
 
lis = [i for i in range(1,K+1)]
a = 0
 
n = list(itertools.product(lis, repeat=3))
for i in range(len(n)):
    ma = math.gcd(math.gcd(n[i][0],n[i][1]),math.gcd(n[i][0],n[i][2]))
    a += ma
print(a)

### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for l in range(1, k+1):
            ans += gcd(gcd(i, j), l)
print(ans)
### BUGGY CODE ###

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

prefs_list = []
prefs_dict = {}
for i in range(m):
  p, y = map(int, input().split())
  prefs_list.append([p,y])
  if p in prefs_dict:
    prefs_dict[p].append(y)
  else:
    prefs_dict[p] = [y]

for key in prefs_dict:
  prefs_dict[key].sort()

for pref in prefs_list:
  print(str(pref[0]).zfill(6) + str(prefs_dict[pref[0]].index(pref[1])+1).zfill(6))




### FIXED CODE ###

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

prefs_list = []
prefs_dict = {}
for i in range(m):
  p, y = map(int, input().split())
  prefs_list.append([p,y])
  if p in prefs_dict:
    prefs_dict[p].append(y)
  else:
    prefs_dict[p] = [y]

for key in prefs_dict:
  prefs_dict[key].sort()



for pref in prefs_list:
  print(str(pref[0]).zfill(6) + str(bisect.bisect_left(prefs_dict[pref[0]], pref[1])+1).zfill(6))
### BUGGY CODE ###

import numpy as np
import sys
def input():
	return sys.stdin.readline()[:-1]

def rank(a):
	n, m = len(a), len(a[0])
	#a = np.array([list(map(int, input().split())) for _ in [0]*n])
	if n > m:
		a = a.T
		n, m = m, n
	r = 0
	for i in range(n):
		if a[i][i] != 1:
			for j in range(i+1, m):
				if a[i][j] == 1:
					a[:, [i, j]] = a[:, [j, i]]
					break
			else:
				for j in range(i+1, n):
					if a[j][i] == 1:
						a[[i, j]] = a[[j, i]]
					break
				else:
					break
		if a[i][i] == 0:
			continue

		r += 1
		for j in range(i+1, m):
			a[:, j] += a[i][j] * a[:, i]
			a[:, j] %= 2
		for j in range(i+1, n):
			a[j] += a[j][i] * a[i]
			a[j] %= 2
	
	return r
	#print((pow(2, n+m-1, MOD) - pow(2, n+m-r-1, MOD)) % MOD)

t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	if s[-1] == "1":
		print(1)
		continue
	else:
		i = 0
		z, zo = [], []
		for i in range(n):
			if s[i] == "1":
				zo.append([(a[i] >> k) & 1 for k in range(60)])
				
			else:
				zo.append([(a[i] >> k) & 1 for k in range(60)])
				z.append([(a[i] >> k) & 1 for k in range(60)])
				
		#print(z, zo)
		if rank(np.array(z)) != rank(np.array(zo)):
			print(1)
		else:
			print(0)

### FIXED CODE ###

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

def least_bit_set(x):
	return x & (-x)


def delete_zeros_from(values, start):
	i = start
	for j in range(start, len(values)):
		if values[j] != 0:
			values[i] = values[j]
			i += 1
	del values[i:]


def eliminate(values):
	values = list(values)
	i = 0
	while True:
		delete_zeros_from(values, i)
		if i >= len(values):
			return values
		j = i
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) < least_bit_set(values[j]):
				j = k
		values[i], values[j] = (values[j], values[i])
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) == least_bit_set(values[i]):
				values[k] ^= values[i]
		i += 1


def in_span(x, eliminated_values):
	for y in eliminated_values:
		if least_bit_set(y) & x != 0:
			x ^= y
	return x == 0



#values = [1, 5, 8, 2, 10]
#eliminated_values = eliminate(values)
#print(eliminated_values)
#x = int(input())
#print(in_span(x, eliminated_values))

t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	values = []
	ok = True
	for i in range(n-1, -1, -1):
		if s[i] == "0":
			values.append(a[i])
		else:
			elim = eliminate(values)
			if not in_span(a[i], elim):
				ok = False
				break
	if ok:
		print(0)
	else:
		print(1)
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=9**9]*h*w
d[~w+a*w+b]=1
q=[(a-1,b-1)]
for s,t in q:
 if s==f-1and t==g-1:break
 p=d[s*w+t]+1
 for y,x in(-1,0),(0,-1),(0,1),(1,0):
  for z in range(k):
   if(h>(i:=s+y*~z)>-1<(j:=t+x*~z)<w)-1or'.'<m[i][j]or d[i*w+j]<p:break
   q+=(i,j),;d[i*w+j]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

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

p = list(map(int,input().split()))
max = 0
for i in range(N-K+1):
    tmp = 0
    tmp += (1+p[i])/2
    for j in range(K-1):
        tmp += (1+p[i+j+1])/2
    if max < tmp:
        max = tmp
        
print(max)




### FIXED CODE ###

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

p = list(map(int,input().split()))
max = 0
for i in range(K):
    max += (1+p[i])/2
tmp = max
for i in range(K,len(p)):
    tmp -= (1+p[i-K])/2
    tmp += (1+p[i])/2
    #print(max)
    if max < tmp:
        max = tmp
    #print(max)    
print(max)




#ロケットペンシル方式