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

H,W = tuple(map(int,input().split()))
P = [[-int(i) for i in input().replace("#","0").replace(".","1")] for i in range(H)]
queue_set = []
for h in range(H):
    for w in range(W):
        if  P[h][w]==0:
            queue_set+=[[h+1,w,0],[h-1,w,0],[h,w-1,0],[h,w+1,0]]
        elif h == 0 or h==H-1 or w==0 or w==W-1:
            queue_set.append([h,w,0])
m = 0
while len(queue_set) != 1:
    h,w,cnt = queue_set.pop(0)
    if 0<=w<W and 0<=h<H and P[h][w] == -1:
        P[h][w] = cnt+1
        a = P[h+1][w] if 0<=h+1<H else -1
        b = P[h-1][w] if 0<=h-1<H else -1
        c = P[h][w+1] if 0<=w+1<W else -1
        d = P[h][w-1] if 0<=w-1<W else -1
        m = max(m,cnt+1 + max(a,b,c,d))
        queue_set+=[[h+1,w,cnt+1],[h-1,w,cnt+1],[h,w-1,cnt+1],[h,w+1,cnt+1]]
print(m)

### FIXED CODE ###

H, W = tuple(map(int, input().split()))
func = (lambda x: 0 if x == "#" else -1)
func_in = (lambda h, w: 0 <= h < H and 0 <= w < W)
P = [[func(i) for i in input()] for i in range(H)]

queue_set = set()
zeros = set()
for h in range(H):
    for w in range(W):
        if P[h][w] == 0:
            zeros.add((h)*W+w)
            for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                if func_in(h+dh, w+dw) and P[h+dh][w+dw] == -1:
                    queue_set.add((h+dh)*W+w+dw)
m = 0

queue = [[q // W, q % W, 0] for q in queue_set]
queue_set |= zeros
idx = 0
cnt = 0
while len(queue) > idx:
    h, w, cnt = queue[idx]
    idx += 1
    cnt += 1
    P[h][w] = cnt
    a = 0
    for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if func_in(h+dh, w+dw) and (h+dh)*W+w+dw not in queue_set:
            queue += [[h + dh, w + dw, cnt]]
            queue_set.add((h+dh)*W+w+dw)
print(cnt)
### BUGGY CODE ###

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

# エラトステネスの篩
#############################################################
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
#############################################################

# 素因数分解、リストで返す
#############################################################
def prime_factorize(n, prime_list):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if f in prime_list and n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a.sort()
    return a
#############################################################

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

data = set(get_sieve_of_eratosthenes(10**6))

primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i], data)
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# print(primes)

if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

# 素因数分解、リストで返す
#############################################################


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a.sort()
    return a
#############################################################


primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# print(primes)

if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

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

# nCr(n, r, m)
mod = 1000000007
n = len(s) + k

fac = [1,1] # 階乗 n!
inv = [0,1] # 逆元 1/n
finv = [1,1] # 逆元の階乗 (n^-1)! = (1/n)!

for i in range(2, n+1):
    fac.append( (fac[-1] * i ) % mod )
    inv.append( (-inv[mod%i] * (mod//i)) % mod )
    finv.append( (finv[-1] * inv[-1]) % mod )

def nCr(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

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

n = len(s)
ans = 0
for i in range(k+1):
    a = modpow(25, i, mod)
    b = modpow(26, k-i, mod)
    c = nCr(n-1+i, n-1, mod)
    ans += a * b * c
    ans %= mod
print(ans)


### FIXED CODE ###

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

# nCr(n, r, m)
mod = 1000000007
n = len(s) + k

fac = [1,1] # 階乗 n!
inv = [0,1] # 逆元 1/n
finv = [1,1] # 逆元の階乗 (n^-1)! = (1/n)!

for i in range(2, n+1):
    fac.append( (fac[-1] * i ) % mod )
    inv.append( (-inv[mod%i] * (mod//i)) % mod )
    finv.append( (finv[-1] * inv[-1]) % mod )

def nCr(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

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

n = len(s)
ans = 0
for i in range(k+1):
    a = modpow(25, i, mod)
    b = modpow(26, k-i, mod)
    c = nCr(n-1+i, n-1, mod)
    ans += a * b * c
    ans %= mod
print(ans)
### BUGGY CODE ###

N,K= map(int,(input().split()))
p = list(map(int,input().split()))
sum_p=[]
for i in range(N-K+1):
  temp_p=0
  for j in range(K):
    temp_p+=p[i+j]
  sum_p.append(temp_p)
msp=max(sum_p)
ans=(msp/2)+(0.5*K)
print(ans)

### FIXED CODE ###

N,K= map(int,(input().split()))
p = list(map(int,input().split()))
rui_p=[]
rui_p.append(0)
sum_p=[]
for i in range(N):
  rui_p.append(rui_p[i]+p[i])
for j in range(K,N+1):
  sum_p.append(rui_p[j]-rui_p[j-K])

msp=max(sum_p)
ans=(msp/2)+(0.5*K)
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(input())

ww = [0]*n
ee = [0]*n

for i in range(n):
  for j in range(0, i+1):
    if s[j] == 'W':
      ww[i] += 1
    else:
      ee[i] += 1
      
l = [0]*n
l[0] = max(ee[1:])
l[n-1] = max(ww[:n-1])
for i in range(1,n-1):
  l[i] = ww[i-1] + ee[-1] - ee[i]
    
  
print(min(l))


### FIXED CODE ###

import sys

n, s = sys.stdin.read().split()

def main():
    cnt = s.count('E')
    cur = 'E'
    res = [cnt]
    for c in s:
        if cur == 'W': cnt += 1
        if c == 'E': cnt -= 1
        res.append(cnt)
        cur = c
    print(min(res))
    
if __name__ ==  '__main__':
    main()
### BUGGY CODE ###

n, q = map(int, input().split())
s = input().rstrip()
sb = s.encode()

for _ in range(q):
  i, r = map(int, input().split())
  print(sb[i-1:r].count(b'AC'))

### FIXED CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()

    lis = [0 for _ in range(len(S))]
    for i in range(len(S)):
        if i > 0:
            lis[i] += lis[i - 1]
        if i < len(S) - 1 and S[i] == 'A' and S[i + 1] == 'C':
            lis[i + 1] += 1

    for _ in range(Q):
        L = tuple(map(int, input().split()))
        print(lis[L[1] - 1] - lis[L[0] - 1])


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

a,b,m=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

ans=99999999999
for i in range(a):
    for j in range(i,b):
        ans=min(ans,A[i]+B[j])
for i in range(m):
    x,y,c=map(int,input().split())
    ans=min(ans,A[x-1]+B[y-1]-c)
print(ans)


### FIXED CODE ###

a,b,m=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

ans=99999999999
ans=min(A)+min(B)
for i in range(m):
    x,y,c=map(int,input().split())
    ans=min(ans,A[x-1]+B[y-1]-c)
print(ans)
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
all_li = []
for i,l in enumerate(li):
    if i == 0:
        continue
    left = sum(li[:i])
    right = sum(li[i:])
    #print(i,left,right)
    all_li.append(abs(left-right))
print(min(all_li))

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
s = sum(li)
sum_li = []
for i,l in enumerate(li):
    if i == 0:
        sum_li.append(l)
        continue
    sum_li.append(sum_li[-1]+l)
all_li = []
for ii,ss in enumerate(sum_li):
    if ii == len(sum_li)-1:
        break
    all_li.append(abs(s-2*ss))
#print(all_li)
print(min(all_li))
### BUGGY CODE ###

from pprint import pprint
import queue

def solve(n, a, b):
    b_pq = queue.PriorityQueue()
    b_rev = {}
    for i, b_i in enumerate(b):
        b_pq.put((-1 * b_i, i))

    count = 0
    while not b_pq.empty():
        tmp = b_pq.get()
        # pprint(tmp)
        b_i = tmp[0] * -1
        i_b = tmp[1]
        # print(i_b, b_i)
        i_a = (i_b - 1 + n) % n
        i_c = (i_b + 1) % n
        b_cand = b_i
        if b_cand - b[i_a] - b[i_c] < a[i_b]:
            continue

        while b_cand - b[i_a] - b[i_c] >= a[i_b]:
            b_cand = b_cand - b[i_a] - b[i_c]
            count += 1

        b[i_b] = b_cand
        b_pq.put((-1 * b_cand, i_b))
        # print("count: ", count)
        # pprint(b)
        if b_cand == a[i_b] and b == a:
            return count
    
    return -1


if __name__ == '__main__':

    n = int(input().strip())
    a = list(map(int, input().strip().split(" ")))
    b = list(map(int, input().strip().split(" ")))
    print(solve(n, a, b))

### FIXED CODE ###

from pprint import pprint
import heapq

def solve(n, a, b):
    b_pq = []
    b_rev = {}
    delete = []
    for i, b_i in enumerate(b):
        if b_i == a[i]:
            continue
        heapq.heappush(b_pq, (-1 * b_i, i))

    count = 0
    while b_pq:
        tmp = heapq.heappop(b_pq)
        # pprint(tmp)
        b_i = tmp[0] * -1
        i_b = tmp[1]
        # print(i_b, b_i)
        i_a = (i_b - 1 + n) % n
        i_c = (i_b + 1) % n
        b_cand = b_i
        if b_cand - b[i_a] - b[i_c] < a[i_b]:
            continue

        #while b_cand - b[i_a] - b[i_c] >= a[i_b]:
        #    b_cand = b_cand - b[i_a] - b[i_c]
        #    count += 1
        tmp_count =  (b_cand - a[i_b]) // (b[i_a] + b[i_c])
        b_cand -= (b[i_a] + b[i_c]) * tmp_count
        count += tmp_count

        b[i_b] = b_cand
        if b_cand != a[i_b]:
            heapq.heappush(b_pq, (-1 * b_cand, i_b))
        # print("count: ", count)
        # pprint(b)
         

        if b_cand == a[i_b] and b == a:
            return count
    
    return -1


if __name__ == '__main__':

    n = int(input().strip())
    a = list(map(int, input().strip().split(" ")))
    b = list(map(int, input().strip().split(" ")))
    print(solve(n, a, b))
### BUGGY CODE ###

from heapq import heappop, heappush

n,k = map(int,input().split())
a = sorted(map(int, input().split()), reverse=True)
f = sorted(map(int, input().split()))

heap = []
for aa,ff in zip(a,f):
    heappush(heap, [-aa*ff, aa, ff])

for _ in range(k):
    cost, aa, ff = heappop(heap)
    if aa == 0:
        break
    aa -= 1 
    heappush(heap, [-aa*ff, aa, ff])
print(-min(heap)[0])


### FIXED CODE ###

def binary_search(a, f, target, left, right):
    ans = a[-1] * f[-1]
    while left + 1 < right:
        mid = (left+right)//2
        cost = 0
        for aa,ff in zip(a,f):
            if ff > mid:
                cost += aa
            elif aa - mid // ff > 0:
                cost += aa - mid // ff
        if cost > target:
            left = mid
        else:
            right = mid
    return right

n,k = map(int,input().split())
a = sorted(map(int, input().split()), reverse=True)
f = sorted(map(int, input().split()))
target = binary_search(a,f,k,-1,max(a) * max(f))
mx = 0
cost = 0
for aa, ff in zip(a,f):
    if ff > target:
        cost += aa
        aa = 0
    elif aa - target // ff > 0:
        cost += aa - target // ff
        aa = (target // ff)
    if mx < aa * ff:
        mx = aa * ff
print(mx)
### BUGGY CODE ###

N = int(input())
for i in range(N):
    count = 0
    for x in range(1, 100):
        if 2 * ((x + 1) ** 2) + 4 > 2 * N:
            break
        for y in range(x, 100):
            if ((x + y) ** 2 + (y + 1) ** 2 + (1 + x) ** 2) > 2 * N:
                break
            for z in range(y, 100):
                # print(x, y, z)
                score = ((x + y) ** 2 + (y + z) ** 2 + (z + x) ** 2)
                if score == 2 * (i + 1):
                    if x == y == z:
                        count += 1
                    elif x == y or y == z:
                        count += 3
                    else:
                        count += 6
                if score > 2 * (i + 1):
                    break
    print(count)


### FIXED CODE ###

N = int(input())
count = [0] * (N + 1)
for x in range(1, 100):
    if 2 * ((x + 1) ** 2) + 4 > 2 * N:
        break
    for y in range(1, 100):
        if ((x + y) ** 2 + (y + 1) ** 2 + (1 + x) ** 2) > 2 * N:
            break
        for z in range(1, 100):
            # print(x, y, z)
            score = ((x + y) ** 2 + (y + z) ** 2 + (z + x) ** 2) // 2
            if score > N:
                break
            else:
                count[score] += 1
for i in range(1, N + 1):
    print(count[i])
### BUGGY CODE ###

n=int(input())
a = [int(_) for _ in input().split()]
for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

import collections

n=int(input())
a = [int(_) for _ in input().split()]

c=collections.Counter(a)
for i in range(1,n+1):
    print(c[i])
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = 1
 
for i in range(n):
    ans = ans*A[i]
    if 0 in A:
        ans = 0
    elif ans > 10**18:
        ans = -1
        break
 
print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = 1

if 0 in A:
  ans = 0
else:
  for i in range(n):
    ans = ans*A[i]
    if ans > 10**18:
        ans = -1
        break
 
print(ans)
### BUGGY CODE ###


N,W = map(int,input().split())
weight = [0]
value = [0]
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
    
maxValue = sum(value)
dp = [[float("inf") for i in range(maxValue+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(1,N+1):
    for v in range(1,maxValue+1):
        dp[i][v] = dp[i-1][v]
        if value[i] <= v:
            dp[i][v] = min(dp[i][v],weight[i] + dp[i-1][v-value[i]])
ans = 0
for x in range(maxValue+1):
    if dp[N][x] <= W:
        ans = x
print(ans)

### FIXED CODE ###

N,W = map(int,input().split())
weight = [0]
value = [0]
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
    
maxValue = sum(value)
INF = 10**10
dp = [[INF for i in range(maxValue+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(1,N+1):
    for v in range(1,maxValue+1):
        if value[i] <= v:
            dp[i][v] = min(dp[i-1][v],weight[i] + dp[i-1][v-value[i]])
        else:
            dp[i][v] = dp[i-1][v]
ans = 0
for x in range(maxValue+1):
    if dp[N][x] <= W:
        ans = x
print(ans)
### BUGGY CODE ###

import sys

n, k = map(int, input().split())
A = list(map(int, input().split()))

L = [1]
tmp = 1
ct = 0
check = 0
while True:
    x = A[tmp - 1]
    ct += 1
    if x in L or ct > k:
        check = x
        break
    else:
        L.append(x)
        tmp = x
if ct > k:
    print(L[k])
    sys.exit()
p = L.index(check)
l = len(L)
roop = l - p
if k < p:
    print(L[k])
else:
    k -= p
    k %= roop
    print(L[p + k])

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))

visit = [-1] * n   #到達しているかどうかを管理

D = [1]  # 循環するもののindexを格納

tmp = A[0]  #初期位置
ct = 1

while visit[tmp - 1] == -1:
    D.append(tmp)
    visit[tmp - 1] = ct  #到達済に変更
    if k == ct:
        print(tmp)
        exit()
    ct += 1
    tmp = A[tmp - 1]

#循環している場合の残りの処理
k -= visit[tmp - 1]
k %= (ct - visit[tmp - 1])
print(D[visit[tmp - 1] + k])
### BUGGY CODE ###

def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]

    for i in range(R):
        for j in range(C):
            v = max(dp[i][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[i+1][j+1][0] = max(dp[i+1][j+1][0], v)
            dp[i+1][j+1][1] = max(dp[i+1][j+1][1], dp[i+1][j][1], dp[i+1][j][0] + u,  v + u)
            dp[i+1][j+1][2] = max(dp[i+1][j+1][2], dp[i+1][j][2], dp[i+1][j][1] + u )
            dp[i+1][j+1][3] = max(dp[i+1][j+1][3], dp[i+1][j][3], dp[i+1][j][2] + u )

    return max(dp[R][C])

if __name__ == '__main__':
    print(main())


### FIXED CODE ###

def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(2)]

    for i in range(R):
        for j in range(C):
            v = max(dp[0][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[1][j+1][0] = max(dp[1][j+1][0], v)
            dp[1][j+1][1] = max(dp[1][j+1][1], dp[1][j][1], dp[1][j][0] + u,  v + u)
            dp[1][j+1][2] = max(dp[1][j+1][2], dp[1][j][2], dp[1][j][1] + u )
            dp[1][j+1][3] = max(dp[1][j+1][3], dp[1][j][3], dp[1][j][2] + u )
        dp[1], dp[0] = dp[0], dp[1]

    return max(dp[0][C])

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


def main():
    N = int(input())
    S = input()

    dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
    ans = 0
    for i in reversed(range(N)):
        for j in reversed(range(N)):
            if S[i] != S[j]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1
            if i >= j: continue
            tmp = min(dp[i][j], j-i)
            ans = max(ans, tmp)


    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    N = int(input())
    S = input()
    ans = 0

    """
    他言語ならこれで行けるはずだが、pythonだとTLE
    dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
    for i in reversed(range(N)):
        for j in reversed(range(i+1,N)):
            if S[i] != S[j]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1
            if i >= j: continue
            tmp = min(dp[i][j], j-i)
            ans = max(ans, tmp)
    """
    i = j = 0

    while  j <= N-1:
        # 頭から見ていき、部分文字列が、その後ろのどこかにあれば範囲を広げる。かぶってはいけないのでj-iが最大
        if S[i:j] in S[j:]:
            ans = max(ans, j-i)
            j += 1
        else:
            i += 1
        

    print(ans)

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

N = int(input())
A = list(map(int, input().split()))
ANS = [0]*len(A)

ansList = []
for i in range(len(A),0,-1):
    if(ANS[i-1]%2!=A[i-1]):
        tList = make_divisors(i)
        for j in tList:
            ANS[j-1]+=1
        ansList.append(i)
print(len(ansList))

for i in ansList:
    print(i, end=" ")


### FIXED CODE ###

import math as math

N = int(input())
A = list(map(int, input().split()))
ANS = [0]*len(A)
for i in range(math.floor(N/2)+1,N):
    ANS[i] = A[i]

fnum=math.floor(N/2)
for i in range(fnum,-1,-1):
    j = i + 1
    tsum=A[i]
    for k in range(j,N+1,j):
        tsum+=ANS[k-1]
    ANS[i]=tsum%2

#print(ANS)
anslist=[]
for i in range(N):
    if ANS[i]==1:
        anslist.append(i+1)
 
print(len(anslist))
for s in anslist:
    print(s, end =" ")
### BUGGY CODE ###

n = int(input())
num_list = list(map(int,input().split()))
result = 1
for i in num_list:
  result = result * i
  

if(result > 10**18):
  result = -1
  
print(result)

### FIXED CODE ###

n = int(input())
num_list = list(map(int,input().split()))
result = 1
if(0 in num_list):
  result = 0
else:
  for i in num_list:
    result = result * i
    if(result > 10**18):
      result = -1
      break
  
print(result)
### BUGGY CODE ###

k, s = map(int, input().split())
cnt=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                cnt+=1

print(cnt)

### FIXED CODE ###

k, s = map(int, input().split())
cnt=0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0<=z and z<=k:
            cnt+=1

print(cnt)
### BUGGY CODE ###

from collections import defaultdict
import heapq
T=int(input())
for testcase in range(T):
    N,A,B,C,D=map(int,input().split())
    dist=defaultdict(lambda:10**23)
    dist[N]=0
    q=[]
    heapq.heappush(q,(0,N,0))
    while(len(q)!=0):
        nowdist,num,onestreak=heapq.heappop(q)
        if dist[num]<nowdist:
            continue
        if dist[0]>dist[num]+num*D:
            dist[0]=dist[num]+num*D
            heapq.heappush(q,(dist[0],0,num*D))
        if num%2==0 and (dist[num//2]>dist[num]+A):
            dist[num//2]=dist[num]+A
            heapq.heappush(q,(dist[num//2],num//2,0))
        if num%3==0 and (dist[num//3]>dist[num]+B):
            dist[num//3]=dist[num]+B
            heapq.heappush(q,(dist[num//3],num//3,0))
        if num%5==0 and (dist[num//5]>dist[num]+C):
            dist[num//5]=dist[num]+C
            heapq.heappush(q,(dist[num//5],num//5,0))
        if onestreak<5 and (dist[num+1]>dist[num]+D):
            dist[num+1]=dist[num]+D
            heapq.heappush(q,(dist[num+1],num+1,onestreak+1))
        if onestreak<5 and num>=1 and (dist[num-1]>dist[num]+D):
            dist[num-1]=dist[num]+D
            heapq.heappush(q,(dist[num-1],num-1,onestreak+1))
    print(dist[0])

    
        
        

### FIXED CODE ###

from collections import defaultdict
import heapq
T=int(input())
for testcase in range(T):
    N,A,B,C,D=map(int,input().split())
    dist=defaultdict(lambda:10**23)
    dist[N]=0
    q=[]
    heapq.heappush(q,(0,N,0))
    while(len(q)!=0):
        nowdist,num,onestreak=heapq.heappop(q)
        if dist[num]<nowdist:
            continue
        if dist[0]>dist[num]+num*D:
            dist[0]=dist[num]+num*D
            heapq.heappush(q,(dist[0],0,num*D))
        if num%2==0 and (dist[num//2]>dist[num]+A):
            dist[num//2]=dist[num]+A
            heapq.heappush(q,(dist[num//2],num//2,0))
        if num%3==0 and (dist[num//3]>dist[num]+B):
            dist[num//3]=dist[num]+B
            heapq.heappush(q,(dist[num//3],num//3,0))
        if num%5==0 and (dist[num//5]>dist[num]+C):
            dist[num//5]=dist[num]+C
            heapq.heappush(q,(dist[num//5],num//5,0))
        if onestreak<5 and (dist[num+1]>dist[num]+D):
            dist[num+1]=dist[num]+D
            heapq.heappush(q,(dist[num+1],num+1,onestreak+1))
        if onestreak<5 and num>=1 and (dist[num-1]>dist[num]+D):
            dist[num-1]=dist[num]+D
            heapq.heappush(q,(dist[num-1],num-1,onestreak+1))
    print(dist[0])
### BUGGY CODE ###

import numpy as np
# スペース区切りの整数の入力
N = int(input())
A = np.array(list(map(int, input().split())))


count = 0
while len(A) > 0:
    a = A[0]
    A = A[1:]
    
    # a で割り切れない部分
    f1 = A % a > 0
    # a を割り切れない部分
    f2 = a % A  > 0 
        
    # 0がなければCountする
    if np.sum(f2 == 0) == 0:
        count += 1

    # AとAinvの不要な箇所を削除
    A = A[f1]

print(count)


### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
D=set()
S=set()
for i in range(N):
    if A[i] in S:
        D.add(A[i]) # ダブったやつ
    else:
        S.add(A[i])# かぶり除去
M=max(S) #最大値
X=[1 for i in range(M+1)] #M個の1のリスト
for a in S:
    if a in D:# かぶってたらフラグ除去
        X[a]=0
    for i in range(2*a,M+1,a): # aのN倍をフラグ除去
        X[i]=0
ans=0
for i in range(N):
    if X[A[i]]==1:
        ans+=1
print(ans)