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

# from math import gcd
from fractions import gcd  # gcd: 2つの正の数を渡すと最大公約数を返す  # Atcoder ではこっち
from collections import defaultdict

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

# 正の公約数
cf=[] # 1が公約数なのは当然
min_num = min(a, b)+1
for i in range(2, min_num):
    if a % i == 0 and b % i == 0:
        cf.append(i)

# print(cf)

# 素数チェック
def is_prime(n):
    """
    Assumes that n is a positive natural number
    https://www.rookieslab.com/posts/fastest-way-to-check-if-a-number-is-prime-or-not
    """
    # We know 1 is not a prime number
    if n == 1:
        return False

    i = 2
    # This will loop from 2 to int(sqrt(x))
    while i*i <= n:
        # Check if i divides x without leaving a remainder
        if n % i == 0:
            # This means that n has a factor in between 2 and sqrt(n)
            # So it is not a prime number
            return False
        i += 1
    # If we did not find any factor in the above loop,
    # then n is a prime number
    return True

# disjoint_dict = defaultdict(lambda: True)

disjoint_dict = {i: True for i in cf}

# for i in range(0, len(cf)-1):

for i, cf_i in enumerate(cf):

    if is_prime(cf_i):  # 素数である
        continue
    if disjoint_dict[cf_i] == False:  # 既に互いに素ではないパターンが発見されている
        continue

    # for j in range(i, len(cf)):
    cf_for_j = cf[i:]
    for cf_j in cf_for_j:
        if disjoint_dict[cf_j] == False:
            continue

        if gcd(cf_i, cf_j) != 1:
            disjoint_dict[cf_j] = False

# print(disjoint_dict)
print(sum(disjoint_dict.values())+1)  # 1は必ず全ての数字に対して互いに素なので +1 する


### FIXED CODE ###

"""
GCD(A, B) の公約数を素因数分解して出てきた素数の数+1 が答え.
"""

import math
from fractions import gcd  # gcd: 2つの正の数を渡すと最大公約数(Greatest Common Divisor)を返す  # Atcoder ではこっち
from collections import OrderedDict


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

# A, B の公約数 = gcd(a, b)の公約数
# GCD
gcd_num = gcd(a, b)

# 素因数分解
"""
N = p * q    (p <= q, pとqは素因数) の時
p <= sqrt(N)    となる

つまり, sqrt(N) まで試して, 割り切れなかった(残った)ものは素因数と言える.
言い方を変えると, sqrt(N)以上の素因数は高々1個まで.

これから, 順番に割っていくのをsqrt(N)までやり, 残ったのが1じゃなければそれも素数.
これなら計算量 O(sqrt(N)) でいける.
"""
def factorize(n):
    """素因数分解を行う

    Parameters
    ----------
    n : int
        正の自然数
    """
    res = dict()
    for i in range(2, math.ceil(math.sqrt(n))):
        if n%i:  # 割り切れなかったらcontinue
            continue
        res[i] = 0
        while (n%i == 0):
            n /= i
            res[i] += 1

    if (n != 1):
        res[n] = 1
    return res


res = factorize(gcd_num)
ans = len(res.keys()) + 1  # 1は必ず入る
print(ans)
### BUGGY CODE ###

s = input()
while 1:
    s1 = s.replace('ST','',1)
    if len(s1) == len(s):
        break
    s = s1
print(str(len(s1)))

### FIXED CODE ###

st = input()
sc = 0
tc = 0
for s in st:
    if s == "S":
        sc += 1
    if s == "T":
        if sc > 0:
            sc -= 1
        else:
            tc += 1

print(sc + tc)
### BUGGY CODE ###

A, B, C, D = map(int,input().split())

d={}
for i in range(A,C+1):
  d[(i,B)] = B**(i-A) % 998244353
for j in range(B,D+1):
  d[(A,j)] = A**(j-B) % 998244353
 
for i in range(A+1,C+1):
  for j in range(B+1,D+1):
    d[(i,j)]=(j*d[(i-1,j)]+i*d[(i,j-1)]-(i-1)*(j-1)*d[(i-1,j-1)]) % 998244353
    
print(d[(C,D)] % 998244353)

### FIXED CODE ###

import sys
import numpy as np
#from functools import lru_cache
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
MOD = 998_244_353
 
def main(A, B, C, D):
	d = np.zeros((C + 1, D + 1), np.int64)
	d[A,B]=1
	for i in range(A+1,C+1):
  		d[i,B] = B*d[i-1,B] % MOD
	for j in range(B+1,D+1):
		d[A,j] = A*d[A,j-1] % MOD
 
	for i in range(A+1,C+1):
		for j in range(B+1,D+1):
			d[i,j]=((((j*d[i-1,j]) % MOD + i*d[i,j-1] % MOD) % MOD) -((i-1)*((j-1)*d[i-1,j-1] % MOD)% MOD)% MOD)
    
	return d[C,D] % MOD
          
"""    
    print(d[C][D] % MOD)
    dp = np.zeros((C + 1, D + 1), np.int64)
    dp[C, D] = 1
    for d in range(D, 0, -1):
        dp[C, d - 1] = dp[C, d] * C % MOD
    for c in range(C - 1, -1, -1):
        x = 0
        for d in range(D, -1, -1):
            dp[c, d] = (d * dp[c + 1, d] + x) % MOD
            x += dp[c + 1, d]
            x *= c
            x %= MOD
    return dp[A, B]
"""

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    signature = (i8, i8, i8, i8)
 
    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()
 
from my_module import main
 
A, B, C, D = map(int, read().split())
print(main(A, B, C, D))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify

N,Q=map(int, sys.stdin.readline().split())

RW=[]	#  Roadwork: 道路工事を行っている場所　(開始時間、終了時間、x座標)
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	RW.append( (max(0,s-x) , max(0,t-1-x),x) )

RW.sort(key=lambda x:(x[2]) )

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]	# Q人の歩き出す時刻
D.sort()


d=0
for d in D:
	hq=[]
	for s,t,x in RW:
		if s<=d<=t:
			heappush(hq, x)

		if hq:
			print hq[0]
			break
	else:
		print -1


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right

N,Q=map(int, sys.stdin.readline().split())

S=[]
event=[]	#x, s, t
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	heappush( event, (x, max(0,s-x) , max(0,t-1-x)) )


D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
D.sort()
ans=[ float("inf") for _ in range(Q) ]

Next=[ i+1 for i in range(Q) ]	#Next


while event:
	x,s,t=heappop(event)
	start=bisect_left(D,s)
	end=bisect_right(D,t)

	i=start
	while i<end:
		ans[i]=min(ans[i],x)
		next=Next[i]
		Next[i]=end
		i=next

for x in ans:
	if x==float("inf"):
		print -1
	else:
		print x
### BUGGY CODE ###

#abc142C_go to school
N = int(input())
A = list(map(int, input().split()))
ans = [] 
for i in range(1,N+1):
    ans.append(A.index(i)+1)    
print(*ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
L = [[] for i in range(N)]
for i in range(N):
    L[i] = [A[i], i+1]
L.sort()
ans = [0 for i in range(N)]
for i in range(N):
    ans[i] = L[i][1]
print(*ans)
### BUGGY CODE ###

H, W, M = map(int, input().split())
hallline = {}
for i in range(H):
    hallline[i] = 0
wallline = {}
for j in range(W):
    wallline[j] = 0
b = [[False for i in range(W)] for j in range(H)]

for i in range(M):
    tmp = list(map(lambda x: int(x) - 1, input().split()))
    hallline[tmp[0]] += 1
    wallline[tmp[1]] += 1
    b[tmp[0]][tmp[1]] = True

t = max(hallline.values())
s = max(wallline.values())

hkeys = [k for k, v in hallline.items() if v == t]
wkeys = [k for k, v in wallline.items() if v == s]

for i in hkeys:
    for j in wkeys:
        if not b[i][j]:
            print(t + s)
            exit()
print(t + s - 1)


### FIXED CODE ###

H, W, M = map(int, input().split())
hallline = [0 for i in range(H)]
wallline = [0 for i in range(W)]
b = {}

for i in range(M):
    tmp = list(map(lambda x: int(x) - 1, input().split()))
    hallline[tmp[0]] += 1
    wallline[tmp[1]] += 1
    b[(tmp[0], tmp[1])] = True

t = max(hallline)
s = max(wallline)

a = [i for i in range(H) if hallline[i] == t]
c = [i for i in range(W) if wallline[i] == s]

tmp = False

for i in a:
    for j in c:
        if (i, j) not in b.keys():
            print(t + s)
            tmp = True
            break
    if tmp:
        break
if not tmp:
    print(t + s - 1)
### BUGGY CODE ###

n = int(input())
s = input()
min_c = 9999999

w_cnt = s.count("W")
e_cnt = s.count("E")

if w_cnt > e_cnt:
   for i in range(int(n/2)+1):
      if i == 0:
         cnt = s.count("E")
         if s[0] == "E":
            cnt = cnt - 1
      elif i == n -1:
         cnt = s.count("W")
         if s[n-1] == "W":
            cnt -= 1
      else: 
         a = s[:i]
         b = s[i+1:]
         a_cnt = a.count("W")
         if a_cnt > min_c: continue
         b_cnt = b.count("E")
         if b_cnt > min_c: continue
         cnt = a_cnt + b_cnt
         if cnt > min_c: continue
      min_c = min(min_c, cnt)
else:
   for i in range(int(n/2)+2, n):
      if i == 0:
         cnt = s.count("E")
         if s[0] == "E":
            cnt = cnt - 1
      elif i == n -1:
         cnt = s.count("W")
         if s[n-1] == "W":
            cnt -= 1
      else: 
         a = s[:i]
         b = s[i+1:]
         a_cnt = a.count("W")
         if a_cnt > min_c: continue
         b_cnt = b.count("E")
         if b_cnt > min_c: continue
         cnt = a_cnt + b_cnt
         if cnt > min_c: continue
      min_c = min(min_c, cnt)

print(min_c)

### FIXED CODE ###

def solve():
    n = int(input())
    s = input()

    cnt = [s[1:n].count("E")]

    for i in range(1, n):
        cnt.append(cnt[i-1] - int(s[i] is "E") + int(s[i-1] is "W"))

    print(min(cnt))

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

import sys

rl = sys.stdin.readline

N, W = map(int, rl().split())
li1 = [map(int, rl().split()) for _ in range(N)]
dp = [-1]*(W+1)
dp[0] = 0
for w, v in li1:
    for i in range(W-w, -1, -1):
        dpi = dp[i]
        if dpi == -1:
            continue
        if dp[i+w] < dpi + v:
            dp[i+w] = dpi + v
print(max(dp))



### FIXED CODE ###

import sys
rl = sys.stdin.readline
def a():
    N, W = map(int, rl().split())
    dp = [-1]*(W+1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, rl().split())
        for i in range(W-w, -1, -1):
            dpi = dp[i]
            if dpi == -1:
                continue
            if dp[i+w] < dpi + v:
                dp[i+w] = dpi + v
    print(max(dp))
a()
### BUGGY CODE ###

def main():
    from collections import defaultdict
    N = int(input())
    *a, = map(int, input().split())

    d = defaultdict(int)
    for x in a:
        d[x] += 1

    for x in a:
        t = 0
        d[x] -= 1

        for key, value in d.items():
            t += value * (value - 1) // 2

        d[x] += 1

        print(t)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


### FIXED CODE ###

def main():
    N = int(input())
    *a, = map(int, input().split())

    d = [0] * (N + 1)
    for x in a:
        d[x] += 1

    b = 0
    for x in d:
        b += x * (x - 1) // 2

    for x in a:
        t = b - (d[x] - 1)

        print(t)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
print(max([len(list(filter(lambda x: i-1 <= x and x <= i+1, a))) for i in set(a)]))

### FIXED CODE ###

import collections
N = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
print(max([c[i-1]+c[i]+c[i+1] for i in set(a)]))
### BUGGY CODE ###

from collections import deque
N,M=list(map(int,input().split()))
AB=[set() for i in range(N+1)]
room=[0]*(N+1)
pre=[None]*(N+1)
def bfs(i):#１に到達
    Done=set()
    Done.add(i)
    d=deque([i])
    child=set()
    child.add(i)
    count=1
    while(d):
        k=d.popleft()
        if k not in child:
            count+=1
            child=child.union(Done)
        room[k]=count
        for i in AB[k]:
            if i not in Done:
                pre[i]=k
                Done.add(i)
                d.append(i)





for i in range(M):
    A,B=list(map(int,input().split()))
    AB[A].add(B)
    AB[B].add(A)

flag=True
bfs(1)
if sum(room)==0:
    print("No:")
    exit()
for i in range(2,N+1):
    if flag:
        print("Yes")
        flag=False
    if pre[i] is not None:
        print(pre[i])




### FIXED CODE ###

from collections import deque
N,M=list(map(int,input().split()))
AB=[set() for i in range(N+1)]
room=[0]*(N+1)
pre=[None]*(N+1)
def bfs(i):#１に到達
    Done=set()
    Done.add(i)
    d=deque([i])
    # child=set()
    # child.add(i)
    # count=1
    while(d):
        k=d.popleft()
        # if k not in child:
        #     count+=1
        #     child=child.union(Done)
        # room[k]=count
        for i in AB[k]:
            if i not in Done:
                pre[i]=k
                Done.add(i)
                d.append(i)





for i in range(M):
    A,B=list(map(int,input().split()))
    AB[A].add(B)
    AB[B].add(A)

flag=True
bfs(1)
if pre.count(None)<=N+1:
    for i in range(2,N+1):
        if flag:
            print("Yes")
            flag=False
        if pre[i] is not None:
            print(pre[i])
else:print("No")
### BUGGY CODE ###


input()
xs = map(int, input().split())

d = dict()
for x in xs:
    if x in d.keys():
        d[x] += 1
    else:
        d[x] = 1

res = 0
for x, c1 in d.items():
    if c1 >= 4:
        if res < x * x: res = x * x
    for y, c2 in d.items():
        if x != y and c1 >= 2 and c2 >= 2:
            if res < x * y: res = x * y


print(res)


### FIXED CODE ###


input()
xs = map(int, input().split())

d = dict()
for x in xs:
    if x in d.keys():
        d[x] += 1
    else:
        d[x] = 1

res = 0
for x, c1 in d.items():
    if c1 >= 4:
        if res < x * x: res = x * x

v = sorted(list(map(lambda s: s[0], (filter(lambda x: x[1] >= 2, d.items())))), reverse=True)

if len(v) >= 2:
    if res < v[0] * v[1]: res = v[0] * v[1]

"""
    for y, c2 in d.items():
        if x != y and c1 >= 2 and c2 >= 2:
            if res < x * y: res = x * y
"""


print(res)
### BUGGY CODE ###


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

P=[1]
now=1

for i in range(K):
    now=A[now-1]
    if now in P:
        x = i+1
        y = P.index(now)
        break
    elif i == K-1:
        print(now)
        exit()

c=(K-y)%(x-y)

for i in range(c):
    now=A[now-1]

print(now)

### FIXED CODE ###


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

P=[1]
S=[0]*N
S[0]=1
now=1

for i in range(K):
    now=A[now-1]
    if S[now-1]==1:
        x = i+1
        y = P.index(now)
        break
    elif i == K-1:
        print(now)
        exit()
    else:
        P.append(now)
        S[now-1]=1

c=(K-y)%(x-y)

print(P[y+c])
### BUGGY CODE ###

import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i] += i+1,
    g[i+1] += i,
g[x-1] += y-1,
g[y-1] += x-1,

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)

ans = [0]*n
for start in range(n):
    dist = [-1] * n
    dist[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    add,pop = q.append,q.popleft
    while q:
        # v = que.get()
        v = pop()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v]+1
                # que.put(nv)
                add(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
# for i in range(1,n):
#     # print(int(np.count_nonzero(d==i)/2))
#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in ans[1:]))


### FIXED CODE ###

def main():
    from collections import deque
    n,x,y=map(int,input().split())
    e=[[]for _ in range(n)]
    for i in range(n-1):
        e[i]+=i+1,
        e[i+1]+=i,
    e[x-1]+=y-1,
    e[y-1]+=x-1,
    a=[0]*n
    for s in range(n):
        d=[-1]*n
        d[s]=0
        q=deque([s])
        add,pop=q.append,q.popleft
        while q:
            v=pop()
            for w in e[v]:
                if d[w]<0:
                    d[w]=d[v]+1
                    add(w)
        for i in d:a[i]+=1
    print(' '.join(str(i//2)for i in a[1:]))
main()
### BUGGY CODE ###

n = int(input())
s = []
a = []
b = []
count = 0
for i in range(n):
  s.append(input())
  for j in s[0]:
    a.append(j)
  a.sort()
    
  #print(a)
  s.pop(0)
  b.append("".join(a))
  a.clear()

  
  
for i in range(n):
  for j in range(n-i-1):
    if b[i] == b[i+j+1]:
      count += 1

print(count)


### FIXED CODE ###

n = int(input())
d = {}
sum = 0

for i in range(n):
  s = list(input())
  s.sort()
  t = "".join(s)
  s.clear()
  if t in d:
    d[t] += 1
  else:
    d[t] = 1
    
for i in d:
  if d[i] > 1:
    sum += (d[i]*(d[i]-1))/2

print(int(sum))
### BUGGY CODE ###

#!/usr/bin/env python3

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

L = []
R = []
for i in range(N):
    L.append(i+A[i])
    R.append(i-A[i])
ans = 0
for l in L:
    ans += R.count(l)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

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

L = []
R = []
for i in range(N):
    L.append(i+A[i])
    R.append(i-A[i])

C_L = collections.Counter(L)
C_R = collections.Counter(R)
ans = 0
for l, t in C_L.items():
    if l in C_R:
        ans += t*C_R[l]
print(ans)
### BUGGY CODE ###

A,B,C,K=map(int,input().split())

A=[1 for x in range(A)]
B=[0 for x in range(B)]
C=[-1 for x in range(C)]
D=A+B+C

print(sum(D[:K]))


### FIXED CODE ###

A,B,C,K=map(int,input().split())

if A>=K:print(K)
elif A+B>=K:print(A)
else: print(A-(K-(B+A)))
### BUGGY CODE ###

import sys
from fractions import gcd
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, m = LI()
    g = [set() for i in range(n+1)]
    new_g = [set() for i in range(n+1)]
    new_gg = [set() for i in range(n+1)]
    for i in range(m):
        u, v = LI()
        g[u].add(v)
    s, t = LI()
    for i in range(n+1):
        new = set()
        for j in g[i]:
            new = new | g[j]
        new_g[i] = new_g[i] | new

    for i in range(n+1):
        new = set()
        for j in new_g[i]:
            new = new | g[j]
        new_gg[i] = new_gg[i] | new

    last = [list(i) for i in new_gg]

    Q = deque([s])
    searched = [0 for i in range(n+1)]
    searched[s] = 1
    depth = [0 for i in range(n+1)]
    while len(Q) != 0:
        v = Q.popleft()
        for i in last[v]:
            if i == t:
                depth[i] = depth[v] + 1
                print(depth[i])
                return
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                Q.append(i)
                searched[i] = 1
    print(-1)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from fractions import gcd
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, m = LI()
    g = [[] for i in range(3*(n+1))]
    for i in range(m):
        u, v = LI()
        g[u].append(v + n + 1)
        g[u + n + 1].append(v + 2*(n + 1))
        g[u + 2*(n + 1)].append(v)

    s, t = LI()

    Q = deque([s])
    searched = [0 for i in range(3*(n+1))]
    searched[s] = 1
    depth = [0 for i in range(3*(n+1))]
    while len(Q) != 0:
        v = Q.popleft()
        for i in g[v]:
            if i == t:
                depth[i] = depth[v] + 1
                print(depth[i]//3)
                return
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                Q.append(i)
                searched[i] = 1
    print(-1)


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

n = int(input())
a = list(map(int, input().split()))

ans = 1

for i in a:
    ans = ans * i


if ans > 10**18:
    print("-1")
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

ans = 1
a.sort()

for i in a:
    if i == 0:
        ans = 0
        break
    elif ans > 10**18:
        ans = -1
        break
    else:
        ans = ans * i

if ans > 10**18:
    ans = -1
    
print(ans)
### BUGGY CODE ###

from itertools import combinations
from operator  import mul
from functools import reduce
from collections import Counter
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res

    def d(self, n):
        min_factor = self.min_factor
        t = []
        tappend = t.append
        while n > 1:
            if t and t[-1][0] == min_factor[n]:
                t[-1][1] += 1
            else:
                tappend([min_factor[n], 1])
            n //= min_factor[n]
        res = 1
        for _, i in t:
            res *= i + 1
        return res
    
    def div(self, n):
        factors = self.__call__(n)
        res = {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                res |= {reduce(mul, j)}
        return res

if __name__ == "__main__":
    n, *a = map(int, open(0).read().split())
    b, c = set(a), Counter(a)
    P = Osa_k(10**6)
    cnt = 0
    for i in b:
        for d in P.div(i):
            if d != i and d in b:break
        else:cnt += c[i] == 1
    print(1 if n == 1 else cnt)

### FIXED CODE ###

#!/usr/bin/env python3
from collections import Counter
n, *A = map(int, open(0).read().split())
A.sort()
c, s = Counter(A), set()
M = max(A) + 1
ans = 0
for a in A:
    if a in s:
        continue
    ans += c[a] == 1
    for i in range(a, M, a):
        s.add(i)
print(ans)
### BUGGY CODE ###

import math
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7


A_asc = sorted(A)
A_desc = sorted(A, reverse=True)

def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

MAX = 0
MIN = 0
i = 0
r = nCr(n, k)
while r > 0:
    t = nCr(n - 1 - i, k - 1)
    if r > t:
        MAX += (A_desc[i] * t) % mod
        MIN += (A_asc[i] * t) % mod
        r -= t
    else:
        MAX += (A_desc[i] * r) % mod
        MIN += (A_asc[i] * r) % mod
        r -= t
    i += 1

print((MAX - MIN + mod) % mod)

### FIXED CODE ###

import math
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7


def com_init():
    MAX = 10 ** 5 + 1
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init()

def nCr(n,r):
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod 

# def nCr(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


MAX_SUM = 0
MIN_SUM = 0

A.sort() # asc
for j in range(n - k + 1): # 小さい方からk個
    MIN_SUM += A[j] * nCr(n - j - 1, k - 1)

A = A[::-1] # desc
for i in range(n - k + 1): #大きい方からk個
    MAX_SUM += A[i] * nCr(n - i - 1, k - 1)


print((MAX_SUM - MIN_SUM + mod) % mod)