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

M=10**6+1
f=lambda p: exit(print(['pairwise','setwise','not'][p]+' coprime'))
n,*l=map(int,open(0).read().split())
from math import *
g=l[0]
for x in l: g=gcd(g,x)
if g>1: f(2)
C=[0]*M
for x in l: C[x]=1
for i in range(2,M):
  if sum(C[j] for j in range(i,M,i))>1: f(1)
f(0)

### FIXED CODE ###

n=int(input())
l=[*map(int,input().split())]
from math import *
g=l[0]
for x in l:
  g=gcd(g,x)
if g>1: exit(print('not coprime'))
from collections import *
d=Counter()
b=0
for x in l:
  if x%2<1:
    if d[2]:
      b=1
      break
    d[2]=1
  while x%2<1: x//=2
  for i in range(3,int(x**0.5)+1,2):
    if x%i<1:
      if d[i]:
        b=1
        break
      d[i]=1
    while x%i<1: x//=i
    if x<2: break
  if x>1:
    if d[x]:
      b=1
      break
    d[x]=d.get(x,0)+1
print(['pair','set'][b]+'wise coprime')
### BUGGY CODE ###

from math import factorial

def comb(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)

n, m= [int(i) for i in input().split(" ")]

c = []
i = 2
mt = m

while i * i <= mt:
    ci = 0
    while mt % i == 0:
        mt = mt // i
        ci += 1
    if ci > 0:
        c.append(ci)
    i += 1
if mt > 1:
    c.append(1)
    
p = 1
for j in range(0, len(c)):
    p *= comb(n - 1 + c[j], c[j])

print(p % (10**9 + 7))

### FIXED CODE ###

from operator import mul
from functools import reduce

def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n, m= [int(i) for i in input().split(" ")]

c = []
i = 2
mt = m

while i * i <= mt:
    ci = 0
    while mt % i == 0:
        mt = mt // i
        ci += 1
    if ci > 0:
        c.append(ci)
    i += 1
if mt > 1:
    c.append(1)
    
p = 1
for j in range(0, len(c)):
    p *= comb(n - 1 + c[j], c[j])

print(p % (10**9 + 7))
### BUGGY CODE ###

import numpy as np
s=list(input())
n=len(s)
dp_now=np.zeros(13,np.int64)
dp_pre=np.zeros(13,np.int64)
mod=pow(10,9)+7
if s[-1]=='?':
  dp_pre[:10]=1
else:
  dp_pre[int(s[-1])]=1
for i in range(2,n+1):
  dp_now=np.zeros(13,np.int64)
  if s[-i]=='?':
    for j in range(10):
      if (j*pow(10,i-1))%13==0:
        dp_now+=dp_pre
      else:
        dp_now[(j*pow(10,i-1))%13:]+=dp_pre[:-(j*pow(10,i-1))%13]
        dp_now[:(j*pow(10,i-1))%13]+=dp_pre[-(j*pow(10,i-1))%13:]
  else:
    j=int(s[-i])
    if (j*pow(10,i-1))%13==0:
      dp_now+=dp_pre
    else:
      dp_now[(j*pow(10,i-1))%13:]+=dp_pre[:-(j*pow(10,i-1))%13]
      dp_now[:(j*pow(10,i-1))%13]+=dp_pre[-(j*pow(10,i-1))%13:]
  dp_now%=mod
  dp_pre=dp_now.copy()
print(dp_pre[5])


### FIXED CODE ###

def main():
  s=list(input())
  n=len(s)
  dp=[0]*13
  mod=pow(10,9)+7
  if s[-1]=='?':
    dp=[1]*10+[0]*3
  else:
    dp[int(s[-1])]=1
  p_dp=[0]*13
  for i in range(2,n+1):
    if s[-i]=='?':
      for j in range(10):
        a=(j*pow(10,i-1,13))%13
        for k in range(13):
          p_dp[(a+k)%13]+=dp[k]
    else:
      j=int(s[-i])
      a=(j*pow(10,i-1,13))%13
      for k in range(13):
        p_dp[(a+k)%13]+=dp[k]
    
    for k in range(13):
      p_dp[k]%=mod
    dp=[k for k in p_dp]
    p_dp=[0]*13
  print(dp[5])

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())
### BUGGY CODE ###

n = int(input()) 
s = 1
for i in range(n):
    s = s*(i+1)
print(s%((10**9)+7))

### FIXED CODE ###

n = int(input()) 
s = 1
for i in range(n):
    s = (s*(i+1))%((10**9)+7)
print(s%((10**9)+7))
### BUGGY CODE ###

xyzk_, a_, b_, c_ = [input() for _ in range(4)]

x, y, z, k = [int(w) for w in xyzk_.split()]
a_nums = [int(n) for n in a_.split()]
b_nums = [int(n) for n in b_.split()]
c_nums = [int(n) for n in c_.split()]

sums = []
for a in a_nums:
    for b in b_nums:
        for c in c_nums:
            sums.append(a + b + c)

sums.sort(reverse=True)

for n in sums[:k]:
    print(n)


### FIXED CODE ###

xyzk_, *nums_ = [input() for _ in range(4)]

*le, k = [int(w) for w in xyzk_.split()]
abc = [sorted((int(n) for n in w.split()), reverse=True) for w in nums_]

p = [0, 0, 0]
pool = [0, sum(abc[i][p[0]] for i in range(3))]
for _ in range(k):
    max_pool = max(pool)
    max_t = 0
    for i in range(3):
        if p[i] + 1 == le[i]:
            continue
        t = abc[i][p[i] + 1] + abc[(i + 1) % 3][0] + abc[(i + 2) % 3][0]
        if t > max_t:
            max_t = t
            max_3 = i
    if max_pool < max_t:
        p[max_3] = min(p[max_3] + 1, le[max_3] - 1)
        j, k = (max_3 + 1) % 3, (max_3 + 2) % 3
        for n1 in abc[j][:p[j] + 1]:
            for n2 in abc[k][:p[k] + 1]:
                pool.append(n1 + n2 + abc[max_3][p[max_3]])
    print(pool.pop(pool.index(max(pool))))
### BUGGY CODE ###

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


def main():
    N = int(input())
    D = [defaultdict(int) for _ in range(N)]
    for d in D:
        S = list(input()[:-1])
        for s in S:
            d[s] += 1
    # print(D)

    cnt = 0
    for i in range(N-1):
        for j in range(i+1, N):
            if D[i]==D[j]:
                cnt += 1
    
    print(cnt)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from operator import mul
from functools import reduce
from collections import defaultdict
import sys
input = sys.stdin.readline


def cmb(n,r):
    r = min(n-r,r)
    if r < 0: return 0 
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


def main():
    N = int(input())
    d = defaultdict(int)
    for _ in range(N):
        l = sorted(list(input()[:-1]))
        s = ''.join(l)
        d[s] += 1
    # print(d)

    cnt = 0
    for key in d:
        cnt += cmb(d[key], 2)
    
    print(cnt)


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

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

N = int(input())
D = list(map(int,input().split()))
ans = 1
a = 0
if D[0] != 0 or D.count(0) > 1:
  print(0)
  exit()

prev = 1
for i in range (N-2):
  if D.count(i+1) == 0:
    if a < N-1:
      print(0)
      exit()
    else:
      print(ans)
      exit()
  else:
    count = D.count(i+1)
    a += count
    ans = ( ans * pow_k(prev,count) ) %998244353 
    prev = count
print(ans)

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
b = 1
ans = 1
dd=[0]*10**5
for i in d:
    dd[i]+=1
max = max(d)
if d[0] == 0 and d.count(0) == 1:
    for i in range(1, max+1):
        if dd[i] == 0:
            print(0)
            exit()
        if dd[i] == 1:
            ans *= b
        else:
            if b != 1:
                ans *= pow(b, dd[i], 998244353)
        b = dd[i]
    print(ans % 998244353)
else:
    print(0)
### BUGGY CODE ###

N, Q = map(int, input().split(' '))
S = input()
ans = 0
ans_list = []
for i in range(Q):
    l, r = map(int, input().split(' '))
    s = S[l - 1: r]
    cnt = 0
    for i in range(1, len(s), 2):
        if (i + 1) == len(s):
            break
        if s[i] == 'A':
            if s[i + 1] == 'C':
                cnt += 1
        elif s[i] == 'C':
            if s[i - 1] == 'A':
                cnt += 1
    ans_list.append(cnt)
[print(ans) for ans in ans_list]


### FIXED CODE ###

# coding: utf-8
import sys
import itertools


def sr():
    return sys.stdin.readline().rstrip()


def ir():
    return int(sr())


def lr():
    return list(map(int, sr().split()))


N, Q = lr()
S = sr()

ac = [0] * (N - 1)
for i, x in enumerate(zip(S[:], S[1:])):
    if x[0] == 'A' and x[1] == 'C':
        ac[i] = 1

cum = list(itertools.accumulate(ac))
ans_list = []
for _ in range(Q):
    l, r = lr()
    if (l - 2 < 0):
        result = cum[r - 2]
    else:
        result = cum[r - 2] - cum[l - 2]
    ans_list.append(result)
[print(ans) for ans in ans_list]
### BUGGY CODE ###

N = int(input())
ans = []
ansnum = 0
for i in range(N):
    s = input()
    if (s in ans) == False:
        ans.append(s)
        ansnum += 1
print(ansnum)

### FIXED CODE ###

N = int(input())
ans = []
for i in range(N):
    s = input()
    ans.append(s)
answer = set(ans)
print(len(answer))
### BUGGY CODE ###

import sys
import fractions
input = sys.stdin.readline
N = int(input())
list_A = list(map(int, input().split()))
ans = list_A[0]
sum = 0
for i in range(1, N):
    ans *= list_A[i] // fractions.gcd(ans, list_A[i])
if ans == list_A[0]:
    print(N%(7+10**9))
else:
    for a in list_A:
        sum += ans//a
    print(sum%(7+10**9))

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline
N = int(input())
list_A = list(map(int, input().split()))
ans = list_A[0]
sum = 0
for i in range(1, N):
  ans = ans * list_A[i] // fractions.gcd(ans, list_A[i])
for a in list_A:
  sum += ans//a
print(sum%(7+10**9))
### BUGGY CODE ###


def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

N = int(input())

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

mod = 10**9 + 7

s = [2]
now = 3
dic = {}

while now ** 2 <= 10 ** 6:

    flag = True
    for i in s:
        if now % i == 0:
            flag = False
            break

    if flag:
        s.append(now)
    now += 2

for i in s:
    dic[i] = 0

for i in range(N):
    if i > 0 and A[i] == A[i-1]:
        continue
    a = A[i]

    for j in s:
        cnt = 0
        while a % j == 0:
            cnt += 1
            a //= j

        dic[j] = max(dic[j],cnt)

    if a != 1:
        s.append(a)
        dic[a] = 1

lcm = 1

for i in s:
    for j in range(dic[i]):
        lcm *= i
        lcm %= mod

ans = 0
for i in range(N):
    ans += lcm * inverse(A[i],mod)
    ans %= mod
print (ans)


### FIXED CODE ###

import fractions

def lcm(x,y):
  return x // fractions.gcd(x,y) * y


mod = 10**9+7


N = int(input())

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

B = 0
for i in A:
    B += pow(i,mod-2,mod)
    B %= mod

g = 1

for i in range(N):
    g = lcm(g,A[i])

print (g * B % mod)
### BUGGY CODE ###

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

for i in range(int(round(y / 10000, 0))+1):
    for j in range(int(round(y / 5000, 0))+1):
        for k in range(int(round(y / 1000, 0))+1):
            if (10000*i) + (5000*j) + (1000*k) == y and i+j+k == n:
                print(i, j, k)
                exit()

print("-1 -1 -1")

### FIXED CODE ###

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

for i in range(n+1):
    for j in range(n-i+1):
        if (10000*i) + (5000*j) + (1000*(n-i-j)) == y:
            print(i, j, n-i-j)
            exit()

print("-1 -1 -1")
### BUGGY CODE ###

def main():
    #1. input
    m,n = map(int, input().split())
    
    #2. make the list of valid field
    valid_field = list()
    for i in range(1,m+1):
        for j in range(1, n+1):
            valid_field.append([i,j])
    
    #3. judge the number of being turned
    num_being_turned = [0]*len(valid_field)
    cnt = 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            num_being_turned[cnt] = int([i-1,j-1] in valid_field) \
                                                      + int([i-1,j] in valid_field) \
                                                      + int([i-1,j+1] in valid_field) \
                                                      + int([i,j-1] in valid_field) \
                                                      + int([i,j] in valid_field) \
                                                      + int([i,j+1] in valid_field) \
                                                      + int([i+1,j-1] in valid_field) \
                                                      + int([i+1,j] in valid_field) \
                                                      + int([i+1,j+1] in valid_field)
            cnt = cnt+1
                                           
    #4. output
    for i in range(len(num_being_turned)):
        num_being_turned[i] = num_being_turned[i] % 2
    
    print(sum(num_being_turned))

if __name__ == "__main__":
    main()

### FIXED CODE ###

#1. input
# set N<=M 
N, M = map(int, input().split())

if N>M:
    temp = N
    N = M
    M = temp

#2. N=1 -> M-2 (if M=1, ans=1)
#    N=2 -> ans = 0
#    N>3 -> ans = NM - {2(M+N)-4}
if N == 1:
    if M == 1:
        ans = 1
    else:
        ans = M-2
elif N == 2:
    ans = 0
else:
    ans = M*N - 2*(M+N) +4
    
print(ans)
### BUGGY CODE ###

original = input()[::-1]

target = 2019

# s = reversed(original)

counts = [0] * 2019
counts[0] = 1

digit = 1
mod = 0
for c in original:
    val = int(c) * digit
    currentMod = val % target
    mod = (currentMod + mod) % target
    digit *= 10

    counts[mod] += 1
    # count = countOfMod.get(mod, 0) + 1
    # countOfMod[mod] = count
    # if countOfMod[mod] > 1:
    #     results.setdefault(mod, int(count*(count-1)/2))

# print(sum(results.values()))

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans)  # 答えの出力

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

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

NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])
An = sorted(list(map(int,input().split(' '))))
Fn = sorted(list(map(int,input().split(' '))),reverse=True)
An_s = sum(An)
#print(An)
#print(Fn)

min_time = -1 #middle_time = 0を含めるので -1
max_time = An[N-1] * Fn[0] #最大でかかる時間
x_cadidate = An[N-1] * Fn[0] #xの最小の候補
middle_time = -1
range_n = range(N)
#init_list = [0]*N
while True:
    # max_time+1は max_time=0まで求めるため
    middle_time = (min_time + max_time)//2 #二部探索ように 最大と最小の半分を考える この時 middle_time An[i] * Fn[i]の取りうる最大として考える 
    #new_list = init_list
    sum_ax = 0
    for i in range_n:
        ax = middle_time//Fn[i] # An[i] * Fn[i] = x < middle_time より
        if ax < An[i]:
            sum_ax += ax
        else:
            sum_ax += An[i]
    if  min_time+1 == max_time: #An_s - sum_candisum_axdate == K or
        break
    elif An_s - sum_ax <= K:
        if x_cadidate > middle_time:
            x_cadidate = middle_time 
        max_time = middle_time   #もう少し middle_timeを減らせる
    else:
        min_time = middle_time   #もう少し middle_timeは大きい

print(x_cadidate)

### FIXED CODE ###

NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])
An = sorted(list(map(int,input().split(' '))))
Fn = sorted(list(map(int,input().split(' '))),reverse=True)
An_s = sum(An)

min_time = -1 #middle_time = 0を含めるので -1
max_time = An[N-1] * Fn[0] #最大でかかる時間
x_cadidate = An[N-1] * Fn[0] #xの最小の候補
middle_time = -1
range_n = range(N)
#init_list = [0]*N
while True:
    # max_time+1は max_time=0まで求めるため
    middle_time = (min_time + max_time)//2 #二部探索ように 最大と最小の半分を考える この時 middle_time An[i] * Fn[i]の取りうる最大として考える 
    #new_list = init_list
    sum_ax = 0
    for i in range_n:
        ax = middle_time//Fn[i] # An[i] * Fn[i] = x < middle_time より
        if ax < An[i]:
            sum_ax += ax
        else:
            sum_ax += An[i]
    if  min_time+1 == max_time: #二部探索で全てを探索したら終了 
        break
    elif An_s - sum_ax <= K:
        if x_cadidate > middle_time:
            x_cadidate = middle_time 
        max_time = middle_time   #もう少し middle_timeを減らせる
    else:
        min_time = middle_time   #もう少し middle_timeは大きい

print(x_cadidate)
### BUGGY CODE ###

_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = []
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i,j,0))

a = [[-1]*w for _ in range(h)]

while s:
    q, s = s[0], s[1:]
    if a[q[0]][q[1]] != -1:
        continue
    
    a[q[0]][q[1]] = q[2]
    ans = q[2]
    
    if q[0]>0:
        s.append((q[0]-1, q[1], q[2]+1))
    if q[0]<h-1:
        s.append((q[0]+1, q[1], q[2]+1))
    if q[1]>0:
        s.append((q[0], q[1]-1, q[2]+1))
    if q[1]<w-1:
        s.append((q[0], q[1]+1, q[2]+1))
        
print(ans)


### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    m = []
    m.append([True] * (W + 2))
    for _ in range(H):
        m.append([True] + [c == '#' for c in input()] + [True])
    m.append([True] * (W + 2))
    queue = []
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if m[i][j]:
                queue.append((i, j))
    ans = -1
    while queue:
        ans += 1
        tmp = []
        for x, y in queue:
            if not m[x - 1][y]:
                m[x - 1][y] = True
                tmp.append((x - 1, y))
            if not m[x + 1][y]:
                m[x + 1][y] = True
                tmp.append((x + 1, y))
            if not m[x][y - 1]:
                m[x][y - 1] = True
                tmp.append((x, y - 1))
            if not m[x][y + 1]:
                m[x][y + 1] = True
                tmp.append((x, y + 1))
        queue = tmp
    print(ans)

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

n = int(input())
s = input()
t = 0

r = []
g = []
b = []
for n, c in enumerate(s):
    if c == "R":
        r.append(n)
    elif c == "G":
        g.append(n)
    elif c == "B":
        b.append(n)
for x in r:
    for y in g:
        for z in b:
            ary = sorted([x,y,z])
            if (ary[2]-ary[1] != ary[1] - ary[0]):
                t += 1

print(t)


### FIXED CODE ###

n = int(input())
s = input()
t = s.count("R")*s.count("G")*s.count("B")
for i in range(n):
    for j in range(i+1, n):
        k = 2*j - i
        if k < n and s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
            t -= 1

print(t)
### BUGGY CODE ###

n = int(input())
from collections import deque
k = ord('a')
d = deque()
for i in range(26):
  d.append(chr(k + i))
m = 0
while (m<n):
  V = d.popleft()
  for i in range(26):
    d.append(V + chr(k + i))
  m += 1

print(V)


### FIXED CODE ###

sum=26
count=0
n = int(input())
k = ord('a')-1
while(sum<n) :
  count+=1
  sum+=26**(count+1)

current=n
mozi=''
mozi1=''

list1=[]
for i in reversed(range(count+1)) :
  c=current//26**i
  current = current % 26 ** i
  list1.append(c)

for i in range(1,count+1) :
  if list1[-i]<=0 :
    list1[-i]+=26
    list1[-i-1]-=1

for  i in range(count+1) :
  mozi+=chr(list1[i]+k)
print(mozi)
### BUGGY CODE ###

[n,m] = [int(i) for i in input().split()]
a = []
for i in range(m):
    a.append(int(input()))
dp = [0] * (n+1)
dp[0] = 1
if n > 1:
    for i in range(1,n+1):
        if i not in a:
            if i == 1:
                dp[i] = 1
            else:
                dp[i] = (dp[i-2]%(10 ** 9 + 7))+(dp[i-1]%(10 ** 9 + 7))
        else:
            dp[i] = 0
    print((dp[n])%(10 ** 9 + 7))
else:
    if 1 in a:
        print(0)
    else:
        print(1)


### FIXED CODE ###

[n,m] = [int(i) for i in input().split()]
a = []
for i in range(m):
    a.append(int(input()))
ok = [0] * (n+1)
for i in range(m):
    ok[a[i]] = 1
dp = [0] * (n+1)
dp[0] = 1
if n > 1:
    for i in range(1,n+1):
        if ok[i] != 1:
            if i == 1:
                dp[i] = 1
            else:
                dp[i] = (dp[i-2]+dp[i-1])%(10**9+7)
        else:
            dp[i] = 0
    print((dp[n])%(10 ** 9 + 7))
else:
    if 1 in a:
        print(0)
    else:
        print(1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

s = input()
t = input()

#dp[i][j] => s[i], t[j]までの最長部分文字列


dp = [[""] * (len(t) + 1) for j in range(len(s) + 1)]
for j in range(len(t)):
    for i in range(len(s)):
        if s[i] == t[j]:
            v =  [dp[i][j] + s[i], dp[i + 1][j],dp[i][j + 1]]
            v = sorted(v, key = lambda x:len(x))
            dp[i + 1][j + 1] = v[-1]
        else:
            v = [dp[i + 1][j],dp[i][j + 1]]
            v = sorted(v, key = lambda x:len(x))
            dp[i + 1][j + 1] = v[-1]
print(dp[-1][-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
s = input()
t = input()

#dp[i][j] => s[i], t[j]までの最長部分文字列

dp = [[0] * (len(t) + 1) for j in range(len(s) + 1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1] == t[j-1]:
            x = 1
        else:
            x = 0
        dp[i][j] = max(dp[i-1][j-1] + x, dp[i-1][j], dp[i][j-1])


def make_ans(a, b):
    if a ==  0 or b == 0:
        return 
    if s[a-1] == t[b-1]:
        make_ans(a-1,b-1)
        ans.append(s[a-1])
    else:
        if a == 0:
            make_ans(a, b - 1)
        elif b == 0:
            make_ans(a - 1,b)
        else:
            if dp[a - 1][b] > dp[a][b - 1]:
                make_ans(a-1,b)
            else:
                make_ans(a,b-1)

ans = []
make_ans(len(s),len(t))
print("".join(ans))
### BUGGY CODE ###

import bisect


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    tmp = 1
    while tmp * tmp <= n:
        if n % tmp == 0:
            lower_divisors.append(tmp)
            if tmp != n // tmp:
                upper_divisors.append(n // tmp)
        tmp += 1
    return lower_divisors + upper_divisors[::-1]


n = int(input())
*A, = map(int, input().split())
A.sort()
setA = set(A)
cnt = 0
for i, a in enumerate(A):
    if bisect.bisect_right(A, a) - bisect.bisect_left(A, a) != 1:
        cnt += 1
        continue
    X = make_divisors(a)
    if any([x != a and x in setA for x in X]):
        cnt += 1
print(n - cnt)


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
maxA = max(A)
# C[a] = A内のaの個数
C = {a: 0 for a in range(1, maxA + 1)}
for a in A:
    C[a] += 1
# D[a]=1: Aにaより小さいaの約数が存在する
D = {a: 0 for a in range(1, maxA + 1)}
for a in A:
    if C[a] > 0:
        tmp = 2
        while a * tmp <= maxA:
            D[a * tmp] = 1
            tmp += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)
### BUGGY CODE ###

INF = float("inf") #const

def main():
    n,k = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [INF]*n
    dp[0] = 0

    for i in range(n):
        for j in range(1,k+1):
            if i+j >= n:
                break
            else:
                dp[i+j] = min(dp[i+j],dp[i] + abs(h[i]-h[i+j]))

    print(dp[n-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

INF = float("inf") #const

def main():
    n,k = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [INF]*n
    dp[0] = 0

    for i in range(n):
        res = dp[i]
        for j in range(1,k+1):
            if i+j >= n:
                break
            else:
                dp[i+j] = min(dp[i+j],res + abs(h[i]-h[i+j]))

    print(dp[n-1])


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

import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = [-1] + [0]*N
    pvs = set()
    if stack[0] in vs:
        return True
    while stack:
        v, dpd = stack.pop()
        vs.add(v)
        pvs.add(v)

        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack += [(u, dpd)]

    return True

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = defaultdict(int)
    pvs = set()
    while stack:
        v = stack.pop()
        vs.add(v)
        pvs.add(v)
        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack.append(u)
    return True

if __name__ == '__main__':
    from collections import defaultdict
    N, M = map(int, input().split())
    G = defaultdict(set)
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [i+1] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")