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

def main():
    import sys
    input = sys.stdin.buffer.readline
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    S = [0] * (H*W + 1)

    dic = {i: (-1, -1) for i in range(1, H*W + 1)}
    for h in range(H):
        for w in range(W):
            dic[A[h][w]] = (h+1, w+1)

    for d in range(1, D+1):
        for idx in range(d, H*W+1):
            if H*W < idx+D:
                break
            i, j = dic[idx]
            x, y = dic[idx + D]
            S[idx+D] = abs(x - i) + abs(y - j) + S[idx]

    Q = int(input())
    for query in range(Q):
        le, ri = (int(i) for i in input().split())
        print(S[ri] - S[le])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    num_to_xy = {}
    d_sum = [[] for _ in range(D)]
    for h in range(H):
        for w in range(W):
            num_to_xy[A[h][w]] = (h+1, w+1)
            d_sum[A[h][w] % D].append((A[h][w]))
    for d in range(D):
        d_sum[d].sort()
        cur = []
        y, x = -1, -1
        j, i = -1, -1
        for i, a in enumerate(d_sum[d]):
            if i == 0:
                y, x = num_to_xy[a]
                continue
            j, i = num_to_xy[a]
            cur.append(abs(x - i) + abs(y - j))
            y, x = j, i
        s = [0] * (len(cur) + 1)
        for i in range(0, len(cur)):
            s[i+1] = s[i] + cur[i]
        d_sum[d] = s
    Q = int(input())
    for q in range(Q):
        le, ri = (int(i) for i in input().split())
        if le % D != 0:
            print(d_sum[le % D][(ri - le % D)//D] -
                  d_sum[le % D][(le - le % D)//D])
        else:
            print(d_sum[le % D][(ri - le % D)//D-1] -
                  d_sum[le % D][(le - le % D)//D-1])


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

import sys


def new_pow(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return new_pow(x ** 2, n // 2)
    else:
        return x * new_pow(x ** 2, (n - 1) // 2)

input = sys.stdin.readline
n, p = map(int, input().split())
if n == 1:
    ans = p
else:
    ans = 1
    for i in range(2, new_pow(10, 6)+1):
        check = new_pow(i, n)
        if check > p:
            break
        elif p % check == 0:
            ans = i
print(ans)


### FIXED CODE ###

import sys


input = sys.stdin.readline
n, p = map(int, input().split())
if n == 1:
    ans = p
elif n > 10**6:
    ans = 1
else:
    ans = 1
    for i in range(2, 10**6+1):
        check = i**n
        if check > p:
            break
        elif p % check == 0:
            ans = i
print(ans)
### BUGGY CODE ###

from collections import Counter
a=open(0)
n=int(a.readline())
l=a.read().split()
c=Counter(l)
max_list=[kv[0] for kv in c.items() if kv[1]==max(c.values())]
max_list.sort()
print(*max_list,sep="\n")

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
d = {}
for w in s:
    if w not in d:
        d[w] = 0
    d[w] += 1
d2 = sorted(d.items(), key=lambda x:x[1], reverse=True)
maxcnts = [w[0] for w in d2 if w[1] == d2[0][1]]
maxcnts.sort()
for ans in maxcnts:
    print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
q=int(input())
dic=dict()
list_sum=sum(l)
for i in range(len(l)):
    if(l[i] not in dic.keys()):
        dic[l[i]]=1
    else:
        dic[l[i]]+=1
# print(dic)

for i in range(q):
    s=0
    b,c=map(int,input().split())
    if(b in dic.keys() and dic[b]!=0):
        # s=(c-b)*dic[b]+list_sum
        if(c in dic.keys()):
            dic[c]+=dic[b]
            dic[b]=0
        else:
            dic[c]=dic[b]
            dic[b]=0
    for x in dic:
        if(dic[x]!=0):
            s+=x*dic[x]
    print(s)





### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
q=int(input())
dic=dict()
list_sum=sum(l)
for i in range(len(l)):
    if(l[i] not in dic.keys()):
        dic[l[i]]=1
    else:
        dic[l[i]]+=1
# print(dic)
s=list_sum
for i in range(q):
    b,c=map(int,input().split())
    # print(dic)
    if(b in dic and dic[b]!=0):
        s+=(c-b)*dic[b]
        if(c in dic):
            dic[c]+=dic[b]
            dic[b]=0
        else:
            dic[c]=dic[b]
            dic[b]=0
    
    print(s)
    # print(dic)
### BUGGY CODE ###

import numpy as np
s=input()
t=input()
n=len(s)
sl=list(s)
tl=list(t)
l=[sl,tl]


l=np.array(l).T
l=sorted(l,key=lambda x:x[0])
l=np.array(l).T
s=''.join(l[0])
t=''.join(l[1])
a=''
for i in range(n):
    if(s[i]==a):continue
    a=s[i]
    b=t[i]
    s=s.translate(str.maketrans({a:b,b:a}))
    
    
if(s==t):print("Yes")
else:print("No")


### FIXED CODE ###

s=input()
t=input()
n=len(s)



sl=list(s)

sl.sort()
sl=''.join(sl)

a=''
for i in range(n):
    if(sl[i]==a):continue
    a=sl[i]
    b=t[s.index(a)]
    s=s.translate(str.maketrans({a:b,b:a}))
    sl=sl.translate(str.maketrans({a:b,b:a}))
    

if(s==t):print("Yes")
else:print("No")
### BUGGY CODE ###

S = input()
gx, gy = map(int, input().split())
SL = S.split('T')
D = [len(sli) for sli in SL]
DX = D[2::2]
DY = D[1::2]

def reachable(D, s, g):
    OFS = 8000
    dp = [0] * (2*OFS+1)
    dp[OFS+s] = 1
    for i in range(len(D)):
        d = D[i]
        ndp = [0] * (2*OFS+1)
        for j in range(2*OFS+1):
            try:
                ndp[j] += dp[j-d]
            except:
                pass
            try:
                ndp[j] += dp[j+d]
            except:
                pass
        dp = ndp
    return dp[OFS+g] > 0

if reachable(DX, D[0], gx) and reachable(DY, 0, gy):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

S = input()
gx, gy = map(int, input().split())
SL = S.split('T')
D = [len(sli) for sli in SL]
DX = D[2::2]
DY = D[1::2]

def reachable(D, s, g):
    dp = [{} for _ in range(len(D)+1)]
    dp[0][s] = 1
    for i in range(len(D)):
        d = D[i]
        for j in dp[i]:
            dp[i+1][j+d] = 1
            dp[i+1][j-d] = 1
    return g in dp[-1]

if reachable(DX, D[0], gx) and reachable(DY, 0, gy):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from math import factorial


def calc_comb(n, r):
    return factorial(n) // (factorial(n - r) + factorial(r))


def main():
    n = int(input())
    a = [int(an) for an in input().split()]
    a.sort()
    ans1 = 0
    ans2 = 0
    max_comb = 0
    for i in range(1, n):
        sub_set = set()
        for j in range(i):
            sub = a[i] - a[j]
            if not sub in sub_set:
                sub_set.add(sub)
                comb = factorial(a[i]) // (factorial(sub) * factorial(a[j]))
                if comb > max_comb:
                    max_comb = comb
                    ans1 = a[i]
                    ans2 = a[j]
    print(f'{ans1} {ans2}')


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    _ = int(input())
    a = [int(an) for an in input().split()]
    a.sort()
    half_val = -(-a[-1] // 2)
    dist_list = [abs(half_val - an) for an in a[:-1]]
    min_index = dist_list.index(min(dist_list))
    print(f'{a[-1]} {a[min_index]}')


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

N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            ret+=g2(pA,na,x)
        pR=len(nA)-1
        for pa in pA:
            ret+=g2(nA,pa,x)
    elif x==0:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
    else:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
        pR=len(nA)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        pR=len(pA)
        for pa in pA:
            ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=pR
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    pR=over
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=pR
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    pR=r
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0
neg=len(nA)*len(pA)*2
zzz=len(zero)*(N-len(zero)+N-1)

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            while pR>=0:
                if na*pA[pR]>x: break
                pR-=1
            ret+=len(pA)-pR-1
    elif x==0:
        ret+=neg
        ret+=zzz
        ret//=2
    else:
        ret+=neg
        ret+=zzz
        pR=len(nA)-1
        for na in nA:
            while pR>=0:
                if na*nA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if na*na<=x else 0
        pR=len(pA)-1
        for pa in pA:
            while pR>=0:
                if pa*pA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if pa*pa<=x else 0
        ret//=2
    return ret
#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)
### BUGGY CODE ###

N = int(input())
S = input()
length = len(S)
l = list()
for n in range(length-2):
    for m in range(n+1,length):
        for k in range(m+1, length):
            s = S[n]+S[m]+S[k]
            if s not in l:
                l.append(s)
print(len(l))


### FIXED CODE ###

import numpy as np
from collections import Counter
N = int(input())
S = input()
length = len(S)
first = list()
res = 0
for n in range(length-2):
    if S[n] not in first:
        first.append(S[n])
    else:
        continue
    second = list()
    for m in range(n+1, length-1):
        if S[m] not in second:
            second.append(S[m])
        else:
            continue
        third = list()
        for k in range(m+1, length):
            if S[k] not in third:
                third.append(S[k])
            else:
                continue
            res += 1
print(res)
### BUGGY CODE ###

N = int(input())
P = [int(i) for i in input().split()]

c = 0
for i in range(N):
    a = min(P[:i+1])
    if a >= P[i]:
        c += 1
        
print(c)

### FIXED CODE ###

N = int(input())
P = [int(i) for i in input().split()]

c = 0
a = P[0]
for i in range(N):
    a = min(a, P[i])
    if a >= P[i]:
        c += 1
        
print(c)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1, n+1):
    A1 = i
    c =  n//i
    An = A1 + i * (c - 1)
    ans += (A1 + An) * c // 2

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n+1):
    A1 = i
    c =  n//i
    An = A1 + i * (c - 1)
    ans += (A1 + An) * c // 2

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

N = int(input())
A = list(map(int,input().split()))
setA = list(set(A))
mod = 10**9+7
 
import fractions
from functools import reduce
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
 
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
 
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
 
l = lcm(*setA)
B = 0
for i in range(N):
  B += l//A[i]%mod
B %= mod
print(B)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

import fractions
from functools import reduce

def gcd(x,y):
  if x == 0:
    return y
  else:
    return gcd(y-x*(y//x),x)
 

def lcm(x, y):
    return (x*y)//gcd(x,y)
    
l = 1
B = 0

for i in range(N):
  l = lcm(l,A[i])
for i in range(N):
  B += l//A[i]
B %= mod

print(B)
### BUGGY CODE ###

N = int(input())
cnt = [0] * (N+1)

for i in range(1, N+1):
    cnt[i::i] = [j+1 for j in cnt[i::i]]

ans = 0
for i, j in enumerate(cnt):
    ans += i*j
print(ans)

### FIXED CODE ###

def calc(i):
    cnt = n // i
    return (i + i*cnt) * cnt // 2

n = int(input())

ans = 0
for i in range(1, n+1):
    ans += calc(i)

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

import copy
n,m = map(int,input().split())
list1 = [list(map(int,input().split())) for i in range(m)]

list2 = copy.deepcopy(list1)
#int型
def zeropadding(s):
    padding = 6 #何桁揃えにするか入力
    return ("{0:0"+str(padding)+"d}").format(s)
    #returnはstr型なので注意！

#空の多次元リスト
list3 = [[] for i in range(n+1)]

list2.sort()

for i in range(m):
    list3[list2[i][0]].append(list2[i][1])

for i in range(m):
    print(zeropadding(list1[i][0])+zeropadding(list3[list1[i][0]].index(list1[i][1])+1))


### FIXED CODE ###

from copy import deepcopy as dp
from operator import itemgetter as ig
n,m = map(int,input().split())
#[input番号,県番号,年,県における順番]
list1 = []
for i in range(m):
    list1.append([i] + list(map(int,input().split())))

list2 = dp(list1)
list2.sort(key=ig(1,2))
city_number = 0
list2[0].append(city_number)
for i in range(1,m):
    if list2[i][1] == list2[i-1][1]:
        city_number += 1
        list2[i].append(city_number)
    else:
        city_number = 0
        list2[i].append(city_number)
list2.sort(key=ig(0))
for i in range(m):
    print("{0:06d}".format(list2[i][1])+"{0:06d}".format(list2[i][3]+1))
### BUGGY CODE ###

N = int(input())

A = [0 for i in range(N)]
B = [0 for i in range(N)]
C = [0 for i in range(N)]

for i in range(N):
  A[i], B[i] = [int(j) for j in input().split()]
  C[i] = A[i] + B[i]

diff = 0

while len(A) > 0:
  index = C.index(max(C))
  diff += A[index]
  A.pop(index)
  B.pop(index)
  C.pop(index)

  if len(A) == 0:
    break

  index = C.index(max(C))
  diff -= B[index]
  A.pop(index)
  B.pop(index)
  C.pop(index)

print(diff)


### FIXED CODE ###

N = int(input())

A = [[] for i in range(N)]

for i in range(N):
  a, b = [int(j) for j in input().split()]
  c = a + b
  A[i] = [a, b, c]

A.sort(key=lambda x: x[2], reverse=True)

diff = 0

for i in range(N):
  if i % 2 == 0:
    diff += A[i][0]
  else:
    diff -= A[i][1]

print(diff)
### BUGGY CODE ###

N = int(input())
S = input()

counter = 0
for k in range(N):
    for j in range(k):
        if S[k]==S[j]: 
            continue
        else:       
            for i in range(j):
                if  (not S[i]==S[k]) and (not S[j]==S[i]) and (not(j-i==k-j)):
                    counter += 1
                
print(counter)

### FIXED CODE ###

N = int(input())
S = input()
counter = 0

for i in range(N-2):
    for j in range(i+1,(N+i-1)//2+1):
        k = 2*j-i
        if not S[i]==S[j] and  not S[j]==S[k] and not S[i]==S[k]:
            counter += 1

rgb = S.count("R")*S.count("G")*S.count("B")
print(rgb-counter)
### BUGGY CODE ###

K,S= list(map(int, input().split()))
ans=0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k==S:
                ans+=1
                break
print(ans)

### FIXED CODE ###

K,S= list(map(int, input().split()))
ans=0
for i in range(S//3,K+1):
    for j in range(i+1):
        if i+j>S:
            break
        if i+j*2<S:
            continue
        if S-i-j<=j:
            k=S-i-j
            if i==j==k:
                ans+=1
            elif i==j or j==k:
                ans+=3
            else:
                ans+=6
print(ans)
### BUGGY CODE ###

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

dp = [[0 for i in range(n)] for j in range(n)]

for _ in range(m):
    l,r = map(int,input().split())
    dp[l-1][r-1] += 1


for _ in range(Q):
    p,q = map(int,input().split())
    ans = 0
    for i in range(p, q+1):
        for j in range(i, q+1):
            ans += dp[i-1][j-1]
    print(ans)


    
    

### FIXED CODE ###

#a[i][j]
def da_generate(h,w,a):
    da = [[0]*w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1,w):
        da[0][i] = da[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j]+cnt_w
    return da

#da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
def da_calc(p,q,x,y,da):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]

n,m,q = map(int,input().split())
lrl = [[0 for i in range(n)] for j in range(n)]
for _ in range(m):
   l,r = map(int,input().split())
   lrl[l-1][r-1] += 1

da = da_generate(n, n, lrl)

for _ in range(q):
   p,q = map(int,input().split())
   p -= 1
   q -= 1
   print(da_calc(p,p,q,q,da))
### BUGGY CODE ###

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

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
s = [0] *N
for u in range(N-1):
    s[a[u]-1] += 1
for i in range(N):
    print(s[i])
### BUGGY CODE ###

mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

C = [0] * (max(A) + 1)
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in enumerate(C):
    L *= pow(i, c, mod)
    L %= mod

print(L * sum(pow(a, mod - 2, mod) for a in A) % mod)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

    L = reduce(lcm, A)
    print(sum(L // a for a in A) % mod)

main()
### BUGGY CODE ###

def main():
    H, W, K = map(int, input().split())
    chocolate = [list(map(int,list(input()))) for _ in range(H)]
    choco = [[0]*W for _ in range(H)]
    ids = [0] * H
    ans = 10 ** 9
    for bit in range(1<<(H-1)):
        group_id = 0
        for i in range(H):
            ids[i] = group_id
            if (bit>>i)&1:
                group_id += 1
        group_id += 1
        
        for i in range(group_id):
            for j in range(W):
                choco[i][j] = 0

        for i in range(H):
            for j in range(W):
                choco[ids[i]][j] += chocolate[i][j]
        
        if any(choco[i][j] > K for i in range(group_id) for j in range(W)):
            continue
        
        num = group_id - 1
        now = [0] * group_id
        def add(j):
            for i in range(group_id):
                now[i] += choco[i][j]
            if any(now[i] > K for i in range(group_id)):
                return False
            else:
                return True

        for j in range(W):
            if not add(j):
                num += 1
                now = [0] * group_id
                add(j)
        ans = min(ans, num)
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    H, W, K = map(int, input().split())
    chocolate = [list(map(int,list(input()))) for _ in range(H)]
    choco = [[0]*W for _ in range(H)]
    ids = [0] * H
    ans = 10 ** 9
    for bit in range(1<<(H-1)):
        group_id = 0
        for i in range(H):
            ids[i] = group_id
            if (bit>>i)&1:
                group_id += 1
        group_id += 1
        
        for i in range(group_id):
            for j in range(W):
                choco[i][j] = 0

        for i in range(H):
            for j in range(W):
                choco[ids[i]][j] += chocolate[i][j]
        
        if any(choco[i][j] > K for i in range(group_id) for j in range(W)):
            continue
        
        num = group_id - 1
        now = [0] * group_id
        def add(j):
            for i in range(group_id):
                now[i] += choco[i][j]
            if any(now[i] > K for i in range(group_id)):
                return False
            else:
                return True

        for j in range(W):
            if not add(j):
                num += 1
                now = [0] * group_id
                add(j)
        ans = min(ans, num)
    print(ans)


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

import collections
import itertools

N = int(input())
S = input()

ans = 0

for i in range(1,N+1):
  tmp_s_list = list(itertools.combinations(S,i))
  for s in tmp_s_list:
    tmp_count = collections.Counter(s)
    if max(tmp_count.values()) == 1:
      ans += 1

print(ans)

### FIXED CODE ###

import numpy as np

N = int(input())
S = input()

unique_list = list(np.unique(S))

ans = 1

for s in unique_list:
  tmp = S.count(s)
  ans = ans * (tmp + 1)
  
print(int((ans-1) % (10**9 + 7)))
### BUGGY CODE ###

from collections import Counter
n = int(input())
mod = 10**9+7
A = list(map(int,input().split()))
B = max(A)
cnt = [0]*(B+1)
def f(x):
  a = []
  while x % 2 == 0:
    a.append(2)
    x //= 2
  f = 3
  while f * f <= x:
    if x % f == 0:
      a.append(f)
      x //= f
    else:
      f += 2
  if x != 1:
    a.append(x)
  return Counter(a).items()
for i in range(n):
  dct = f(A[i])
  for l in dct:
    if cnt[l[0]] < l[1]:
      cnt[l[0]] = l[1]
ans1 = 1
for i in range(B+1):
  ans1 *= (i**cnt[i])
ans = 0
for i in range(n):
  if A[i] > 0:
    ans += ans1 // A[i]
    ans %= mod
print(ans)

### FIXED CODE ###

from fractions import gcd
def lcm(x,y):
  return (x*y) // gcd(x,y)
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
l = a[0]
for i in range(1,n):
  l = lcm(l,a[i])
ans = 0
for i in range(n):
  ans += l//a[i]
print(ans%mod)
### BUGGY CODE ###

import numpy as np
N = int(input())
n = [x for x in range(1, N+1)]
m = n[1:]
m.append(n[0])
n = np.array(n)
m = np.array(m)
x = n % m
print(sum(x))

### FIXED CODE ###

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

num_all = int(input())
list = input().split(" ")


list_int = []
for j in list:
  list_int.append(int(j))

i = 1
while i <= num_all:
  data = list_int.count(i)
  print(data)
  i = i+1

### FIXED CODE ###

n=int(input())
#l=list(map(int,input().split()))  #inputした数値列をintにしてlistを作成 けどなぜか使えない
list = input().split(" ")
list_int = []
for i in list:
  list_int.append(int(i)) 
k = [0]*n                         #大きさnのリスト
for i in list_int:
  k[i-1] = k[i-1]+1
for j in range(n):
  print(k[j])
### BUGGY CODE ###

def check_prime(k):

    if k == 1:return 1
    for i in rec:
        if i > k // 2:break
        if k % i == 0:return 0
    return 1

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
rec = [a[0]]
double = dict()
for i in range(n):
    if i < n - 1 and a[i] == a[i + 1]:
        double[a[i]] = 1
        rec.append(a[i])
        continue

    if double.get(a[i]):continue
    
    temp = check_prime(a[i])
    if temp:
        rec.append(a[i])
        ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [True] * (a[-1] + 1)
cnt = Counter(a)

for i in range(n):
    if check[a[i]] == False:continue
    for j in range(a[i], a[-1] + 1, a[i]):
        if j == a[i]:continue
        check[j] = False

ans = 0
for i in range(n):
    if check[a[i]] and cnt[a[i]] == 1:ans += 1

print(ans)