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

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
INF = 10**9

c = [INF] * N
c[0] = 0

for i in range(1,N):
  for j in range(max(0, i-K), i):
    c[i] = min(c[j] + abs(h[i] - h[j]), c[i])
print(c[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
INF = 10**9

c = [INF] * N
c[0] = 0

for i in range(N):
  tmp = []
  for j in range(1, min(K, i)+1):
    c[i] = min(c[i-j] + abs(h[i] - h[i-j]), c[i])
print(c[-1])
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
    a[a.index(max(a))] = max(a) // 2
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
    for i in range(m):
        a[0] = a[0] // 2
    print(sum(a))
    exit()

a.sort()
i = 0
while i < m:
    a[n-1] = a[n-1] // 2
    i+=1
    num = len([1 for x in a[:n-1] if x > a[n-1]])
    hoge = min(m-i, num)
    for j in range(hoge):
        a[n-2-j] = a[n-2-j] // 2
    i += hoge
    a.sort()

print(sum(a))
### BUGGY CODE ###

from sys import stdin, setrecursionlimit


def cmb(n, r, mod=10 ** 9 + 7):
    r = min(r, n - r)
    x = y = 1
    for i in range(r):
        x *= n - i
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod


def main():
    mod = 10 ** 9 + 7
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    a.sort()
    ans = 0
    a_cmb = [0] * n
    for i in range(n):
        a_cmb[i] = cmb(i, k - 1, mod)
    for i in range(n - k + 1):
        ans -= a[i] * a_cmb[n - 1 - i]
        ans %= mod
    for i in range(k - 1, n):
        ans += a[i] * a_cmb[i]
        ans %= mod
    print(ans % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

### FIXED CODE ###

from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    a.sort()
    ans = 0

    m = n + 1

    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def initialize_cmb(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                fac[i] = fac[i-1] * i % mod
                inv[i] = mod - inv[mod % i] * (mod // i) % mod
                finv[i] = finv[i - 1] * inv[i] % mod

    def cmb(n, k, mod=10 ** 9 + 7):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

    initialize_cmb(m)

    for i in range(n - k + 1):
        ans -= a[i] * cmb(n - 1 - i, k - 1)
        ans %= mod
    for i in range(k - 1, n):
        ans += a[i] * cmb(i, k - 1)
        ans %= mod
    print(ans % mod)


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

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

# １からNまでの値をもつサイコロを振ったときの期待値
def ex(x:int):
    return (x*(x+1)/2)/x

wa=0
saidai_p=0
for i in range(len(p)-(k-1)):
    if sum(p[i:i+k]) >= wa:
        wa=sum(p[i:i+k])
        saidai_p=i

kitaichi_list=[]
for i in range(k):
    kitaichi_list.append(ex(p[saidai_p+i]))

print (sum(kitaichi_list))

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
ex = [1/2*(i+1) for i in p]
total = [0]

for i in range(N):
    total.append (total[i] + ex[i])

ans = 0
for i in range(N+1-K):
    tmp = total[i+K] - total[i]
    if ans < tmp:
        ans = tmp

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

N,D,A=map(int,input().split())
L=[]
for i in range(N):
    x,h=map(int,input().split())
    L.append([x,h])
L.sort()
ans=0
R=0
F=0
import math
for i in range(N):
    if L[i][1]>0:
        R=L[i][0]+2*D
        ans+=math.ceil(L[i][1]/A)
        F=math.ceil(L[i][1]/A)*A
        for j in range(i+1,N):
            if L[j][0]<=R:
                L[j][1]-=F
    #print(L)
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

N,D,A=map(int,input().split())
L=[]
for i in range(N):
    x,h=map(int,input().split())
    L.append([x,h])
L.sort()

import math

ans=0
S=0
P=0
RL=[0]
RC=[0]
cnt=0
for i in range(N):
    for j in range(P,len(RL)):
        if RL[P]<L[i][0]:
            cnt+=RC[P]
            P+=1
        else:
            break
    if L[i][1]-S+cnt>0:
        ans+=math.ceil((L[i][1]-S+cnt)/A)
        
        RL+=[L[i][0]+2*D]
        RC+=[math.ceil((L[i][1]-S+cnt)/A)*A]
        S+=math.ceil((L[i][1]-S+cnt)/A)*A
    #print(i,ans,P,RL,RC,S,cnt)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
edge = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append(b)
    edge[b].append(a)

imos = [0 for i in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    imos[p] += x

def dfs(v, p):
    for u in edge[v]:
        if u == p:
            continue
        imos[u] += imos[v]
        dfs(u, v)

dfs(0, -1)
print(' '.join([str(x) for x in imos]))


### FIXED CODE ###

from collections import deque

n, q = map(int, input().split())
edge = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append(b)
    edge[b].append(a)

imos = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    imos[p] += x

dq = deque([(0, -1)])
while dq:
    v, p = dq.popleft()
    for u in edge[v]:
        if u == p:
            continue
        imos[u] += imos[v]
        dq.append((u, v))

print(' '.join([str(x) for x in imos]))
### BUGGY CODE ###

def solve(n, w, items):
    # 1-origin
    dp = [[0] * (w + 1) for i in range(n + 1)]

    for i in range(1, n + 1):
        prev = i - 1
        weight, value = items[i - 1][0], items[i - 1][1]
        for j in range(1, w + 1):
            dp[i][j] = dp[prev][j]
            if j - weight >= 0:
                dp[i][j] = max(dp[i][j], dp[prev][j - weight] + value)

    return dp[n][w]


def main():
    n, w = map(int, input().split())

    items = []
    for i in range(n):
        items.append(list(map(int, input().split())))

    ans = solve(n, w, items)
    print(ans)


main()

### FIXED CODE ###

import numpy as np


def solve(w, items):
    dp = np.zeros(w + 1, dtype=int)

    for weight, value in items:
        dp[weight:] = np.maximum(dp[weight:], dp[:w-weight+1] + value)

    return dp[w]


def main():
    n, w = map(int, input().split())
    items = list(list(map(int, input().split())) for _ in range(n))

    ans = solve(w, items)
    print(ans)


main()
### BUGGY CODE ###

H, W = map(int, input().split())
S = [list(input()) + ['_'] for _ in range(H)]
S.append(['_'] * (W+1))

x_seq = [[0] * W for _ in range(H)]
y_seq = [[0] * W for _ in range(H)]

for k in range(H):
    left = 0
    right = 0
    seq = 0
    for i in range(W+1):
        if S[k][i] == '.':
            seq += 1
            right = i+1
        else:
            for j in range(left, right):
                x_seq[k][j] = seq
            seq = 0
            left = i+1
            right = i+1

for k in range(W):
    up = 0
    down = 0
    seq = 0
    for i in range(H+1):
        if S[i][k] == '.':
            seq += 1
            down = i+1
        else:
            for j in range(up, down):
                y_seq[j][k] = seq
            seq = 0
            up = down = i+1

grid = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        grid[i][j] = x_seq[i][j] + y_seq[i][j]
print(max([max(x) for x in grid]) - 1)


### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)])=='.'

R = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)

for i in range(H):
    U[i] = (U[i-1] + 1) * S[i]
    D[-i-1] = (D[-i] + 1) * S[-i-1]

for i in range(W):
    L[:, i] = (L[:, i-1] + 1) * S[:, i]
    R[:, -i-1] = (R[:, -i] + 1) * S[:, -i-1]

print(np.max(R+L+U+D) - 3)
### BUGGY CODE ###

s=input()
dic={}
cur=0
power=1
for i in range(0,len(s)+1):
  s_int=len(s)-i-1
  if cur in dic:
    dic[cur]+=1
  else:
    dic[cur]=1
  try:
    num=int(s[s_int])
    cur+=num*10**power
    cur%=2019
    power+=1
  except IndexError:
    break

res=0
for i in range(len(dic)):
  t=dic.popitem()
  cc=t[1]
  res+=cc*(cc-1)//2
print(res)


### FIXED CODE ###

s=input()
dic={}
cur=0
power=0
for i in range(0,len(s)+1):
  s_int=len(s)-i-1
  if cur in dic:
    dic[cur]+=1
  else:
    dic[cur]=1
  try:
    num=int(s[s_int])
    cur+=num*pow(10,power,2019)
    cur%=2019
    power+=1
  except IndexError:
    break

res=0
for i in range(len(dic)):
  t=dic.popitem()
  cc=t[1]
  res+=cc*(cc-1)//2
print(res)
### BUGGY CODE ###

from time import sleep
 
x = int(input())
a = int(input())
b = int(input())
 
ans = (x-a)%b
 
sleep(x * 0.001)

print(ans)


### FIXED CODE ###

from time import sleep

x = int(input())
a = int(input())
b = int(input())

ans = (x - a) % b

sleep(0)

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

import math
N, P = map(int, input().split())
p = math.ceil(P**(1/N))
ans = 1
flag=False
if N==1:
  print(P)
  exit(0)

if P%2==1:
  flag=True
for i in reversed(range(1, p+1)):
    if flag and i%2==0:
      continue
    if P % (i ** N) == 0:
        ans = i
        break
print(ans)


### FIXED CODE ###

import math
N, P = map(int, input().split())
p = P**(1/N)
ans = 1
flag=False
if N==1:
  print(P)
  exit(0)


divisors=[]

for i in range(2,round(P**(1/N))+1):
  if P%i==0:
    divisors.append(i)
for i in reversed(divisors):
    if P % (i ** N) == 0:
        ans = i
        break
print(ans)
### BUGGY CODE ###

A,B,K = map(int,input().split())
a = []
for i in range(A,B+1):
    a.append(i)
b =set(a[0:K]+a[-K:])
print(' '.join(map(str, sorted(b))))

### FIXED CODE ###

A,B,K = map(int,input().split())
a = []

if B-A<=K:
    for i in range(A,B+1):
        print(i)
else:
    for i in range(A,A+K):
        a.append(i)
    for i in range(B-K+1,B+1):
        a.append(i)
    b =set(a)
    print(' '.join(map(str, sorted(b))))
### BUGGY CODE ###

import numpy as np
import numba
@numba.jit
def solve(n,s):
    dp=np.zeros((n+1,n+1),dtype=np.int16)
    for i in range(n):
        for j in range(i+1,n):
            if s[i]==s[j]:
                if dp[i][j]<j-i:
                    dp[i+1][j+1]=dp[i][j]+1
    print(np.amax(dp))
n=int(input())
s=input()
solve(n,s)

### FIXED CODE ###

n=int(input())
s=input()
dp=[[0]*n for i in range(n)]
for i in range(n-2,-1,-1):
    for j in range(n-1,i,-1):
        if j==n-1:
            if s[j]==s[i]:
                dp[i][j]=1
        else:
            if s[j]==s[i] and dp[i+1][j+1]+1<=j-i:
                dp[i][j]=dp[i+1][j+1]+1
            else:
                dp[i][j]=0
ans=0
for i in range(n):
    for j in range(n):
        ans=max(ans,dp[i][j])
print(ans)
### BUGGY CODE ###

def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, n // 2 + 1):
        if n % i == 0:
            return False
    return True


N = int(input())
print(len(list(filter(isPrime, [int(input()) for i in range(N)]))))



### FIXED CODE ###

import math

def isPrime(n):
    if n <= 2:
        return n == 2
    if (n % 2 == 0):
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

N = int(input())
print(len(list(filter(isPrime, [int(input()) for i in range(N)]))))
### BUGGY CODE ###

import sys
n,m,k =map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

t = k
i = 0
asum = [0]* (n+1)
bsum = [0]* (m+1)
suma = 0
sumb = 0

for  i in range(n):
    suma += a[i]
    asum[i+1]= suma


for  i in range(m):
    sumb += b[i]
    bsum[i+1] = sumb

count = 1
ans = 0

for i in range(n+1):

    for j in range(m+1):
        if asum[i] + bsum[j]<=k and i+j>ans:
            ans=i+j

print(min(ans,m+n))




### FIXED CODE ###

import sys
n,m,k =map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

t = k
i = 0
asum = [0]* (n+1)
bsum = [0]* (m+1)
suma = 0
sumb = 0

for  i in range(n):
    suma += a[i]
    asum[i+1]= suma


for  i in range(m):
    sumb += b[i]
    bsum[i+1] = sumb

count = 1
ans = 0

for i in range(n+1):
    if ans < i :
        if asum[i] <= k:
            ans=i
    else:
        for j in range(ans-i,m+1,1):
            if asum[i] + bsum[j]<=k:
                if i+j>ans:
                    ans=i+j
            else:
                break

print(min(ans,m+n))
### BUGGY CODE ###

n = int(input())
a = [i for i in map(int, input().split())]

for j in range(1, n+1):
  print(a.count(j))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans= [0] * n
         
for i in range(n-1):
    ans[a[i] - 1] += 1

for j in range(n):
    print(ans[j])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

H,W = map(int,readline().split())

grid = [None] * H
dist = [[2000] * W for i in range(H)]
from collections import deque
q = deque([])
for i in range(H):
  grid[i] = readline().rstrip()
  for j in range(len(grid[i])):
    if grid[i][j] == "#":
      q.append((i,j,0))

cases = ((0,1),(0,-1),(1,0),(-1,0))
ans = 0
seen = set()
while q:
  y,x,d = q.popleft()
  if dist[y][x] <= d:
    continue
  dist[y][x] = d
  seen.add((y,x))
  if ans < d:
    ans = d
  for c in cases:
    if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
      if (y + c[0],x + c[1]) in seen:
        continue
      q.append((y + c[0],x + c[1],d + 1))
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0

for i in range(0,W-1):
  np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
for i in range(W-1,0,-1):
  np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
for j in range(0,H-1):
  np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
for j in range(H-1,0,-1):
  np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = [input().rstrip()[::-1] for i in range(N)]
S.sort(key=lambda x:-len(x))
P = 2**61 - 1

from collections import defaultdict,Counter
D = defaultdict(lambda: Counter())

ans = 0
for s in S:
    sets = [set()]
    for c in s[::-1]:
        i = ord(c) - ord('a')
        sets.append(sets[-1] | {i})
    sets.reverse()
    nxs = []
    a = 0
    for l,(c,st) in enumerate(zip(s,sets)):
        for j in st:
            na = (a*27 + (j+1)) % P
            nxs.append((na,l))
        i = ord(c) - ord('a') + 1
        a *= 27
        a += i
        a %= P
    if a in D[len(s)-1]:
        ans += D[len(s)-1][a]
    for na,l in nxs:
        D[l][na] += 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = [input().rstrip()[::-1] for i in range(N)]
S.sort(key=len)
P = 2**61 - 1

from collections import defaultdict
D = defaultdict(lambda: [0]*26)

ans = 0
for s in S:
    l = ord(s[-1]) - ord('a')
    a = 0
    tmp = [0] * 26
    for c in s[:-1]:
        i = ord(c) - ord('a')
        if a in D:
            for j in range(26):
                tmp[j] += D[a][j]
        ans += tmp[i]
        tmp[i] = 0
        a = (a*27 + i + 1) % P
    ans += tmp[l]
    D[a][l] += 1

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

X, Y, Z, K = input().split()
X = int(X)
Y = int(Y)
Z = int(Z)
K = int(K)
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
AB = []
for a in range(len(A)):
    for b in range(len(B)):
        AB.append(A[a] + B[b])
AB = sorted(AB, reverse=True)
ABC = []
for ab in range(min(K, len(AB))):
    for c in range(len(C)):
        ABC.append(AB[ab] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
    print(ABC[i])

### FIXED CODE ###

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)
ABC = []
for a in range(len(A)):
    if a+1 > K:
        break
    for b in range(len(B)):
        if b+1 > K:
            break
        elif (a+1)*(b+1) > K:
            break
        for c in range(len(C)):
            if c+1 > K:
                break
            elif (a+1)*(c+1) > K:
                break
            elif (b+1)*(c+1) > K:
                break
            elif (a+1)*(b+1)*(c+1) > K:
                break
            ABC.append(A[a] + B[b] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

N=int(input())
l=[]
S=[input() for _ in range(N)]
x=0
for i in range(N):
    if S[i]  not in l:
        l.append(S[i])
        x+=1
print(x)  

### FIXED CODE ###

N=int(input())
l=[]
S=[input() for _ in range(N)]
S=list(set(S))
print(len(S))
### BUGGY CODE ###

N,M=map(int,input().split())
dic={i+1:[] for i in range(N)}
PY=[]
for i in range(M):
    p,y=map(int,input().split())
    dic[p].append(y)
    PY.append([p,y])
for k,v in dic.items():
    v.sort()
    dic[k]=v
p,y='',''
ans=[]
for py in PY:
    p=str(py[0])
    y=str(py[1])
    born=dic[int(p)].index(int(y))+1
    print('0'*(6-len(p))+p+'0'*(6-len(str(born)))+str(born))

### FIXED CODE ###

N,M=map(int,input().split())
PY=[list(map(int,input().split())) for _ in range(M)]

D={}
for py in PY:
    try:
        if D[py[0]]=='':
            pass
    except:
        D[py[0]]=[py[1]]
        continue
    D[py[0]].append(py[1])

for k in D.keys():
    D[k].sort()

def binary_tree(lst,key):
    left=0
    right=len(lst)-1
    while left<=right:
        mid=(left+right)//2
        if lst[mid]==key:
            return mid+1
        elif lst[mid]<key:
            left=mid+1
        else:
            right=mid-1
    return -1

for py in PY:
    l=D[py[0]]
    ans=str(py[0]).zfill(6)
    ans+=str(binary_tree(l,py[1])).zfill(6)
    print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    print(IsPrime(N))

def IsPrime(N):
    count = 0
    for i in range(N):
        inputNum = int(input())
        if(inputNum == 2):
            count += 1
            continue
        elif(inputNum % 2 == 0):
            continue

        flag = 0
        for j in range(3, int(inputNum/2), 2):
            if(inputNum % j == 0):
                flag = 1
                break
            else:
                continue
        if(flag == 0):
            count += 1
    
    return count

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    print(IsPrime(N))

def IsPrime(N):
    count = 0
    for i in range(N):
        inputNum = int(input())
        if(inputNum == 2):
            count += 1
            continue
        elif(inputNum % 2 == 0):
            continue

        flag = 0
        for j in range(3, int(pow(inputNum, 1/2))+1):
            if(inputNum % j == 0):
                flag = 1
                break
            else:
                continue
        if(flag == 0):
            count += 1
    
    return count

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

import numpy as np
n,k = map(int,input().split())
ls = np.array(list(map(int,input().split())))
inf = float("inf")
dp = [inf] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
p = inf
new = []
for i in range(2,n):
    st = max(0,i-k)
    dp[i] = np.min(dp[st:i]+abs(ls[i]-ls[st:i]))
print(dp[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
dp = [10000000000] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
p = 10000000000
for i in range(2,n):
    for j in range(i-k,i):
        if (dp[j] >= p) or (abs(ls[j] - ls[i]) >= p):
            pass
        else:
            a = dp[j] + abs(ls[j] - ls[i])
            if a < p:
                p = a
                a = 0
            else:
                a = 0
    dp[i] = p
    p = 10000000000
print(dp[n-1])
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_4
# CreatedDate:  2020-07-20 00:18:24 +0900
# LastModified: 2020-07-20 00:35:29 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n = int(input())
    A = sorted(map(int, input().split()))
    ans = [1 if i in A else 0 for i in range(A[-1]+1)]
    for i, a in enumerate(A):
        if ans[a] == 0:
            continue
        for j in range(i+1, n):
            if A[j]%a == 0:
                ans[A[j]] = 0

    print(sum(ans))

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_3
# CreatedDate:  2020-06-19 15:09:52 +0900
# LastModified: 2020-06-19 15:27:30 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    _ = int(input())
    a_s = list(map(int, input().split()))
    m = max(a_s)+1
    cnt = [0 for _ in range(m)]

    for a in a_s:
        if cnt[a] != 0:
            cnt[a] = 2
            continue
        for n in range(a, m, a):
            cnt[n] += 1

    print(sum(cnt[a] for a in a_s if cnt[a]==1))


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

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        x, y = ns()
        x -= 1
        y -= 1
        e[x].append(y)
        e[y].append(x)

    # dp[i][0]:i番目のノードが白のときの組み合わせの数
    # dp[i][1]:i番目のノードが黒のときの組み合わせの数
    dp = [[1, 1] for _ in range(n)]
    visited = [False for _ in range(n)]

    def dfs(vi, prnt):
        if visited[vi]:
            return
        visited[vi] = True

        for chld in e[vi]:
            if chld == prnt:
                continue
            dfs(chld, vi)

            # 親が白なら子は白でも黒でもいい
            dp[vi][0] *= dp[chld][0] + dp[chld][1]
            dp[vi][0] %= MOD
            # 親が黒田と子は白じゃないとダメ
            dp[vi][1] *= dp[chld][0]
            dp[vi][1] %= MOD

    dfs(0, -1)
    print((dp[0][0] + dp[0][1]) % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
inp = sys.stdin.buffer.readline


def resolve():
    MOD = 10 ** 9 + 7

    n = int(inp())
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        x, y = map(lambda x: int(x) - 1, inp().split())
        e[x].append(y)
        e[y].append(x)

    # dp[i][0]:i番目のノードが白のときの組み合わせの数
    # dp[i][1]:i番目のノードが黒のときの組み合わせの数
    dp = [[1, 1] for _ in range(n)]
    visited = [False for _ in range(n)]

    def dfs(vi, prnt):
        # if visited[vi]:
        #     return
        visited[vi] = True

        for chld in e[vi]:
            if chld == prnt or visited[chld]:
                continue
            dfs(chld, vi)

            # 親が白なら子は白でも黒でもいい
            dp[vi][0] *= (dp[chld][0] + dp[chld][1]) % MOD
            dp[vi][0] %= MOD
            # 親が黒田と子は白じゃないとダメ
            dp[vi][1] *= dp[chld][0] % MOD
            dp[vi][1] %= MOD

    dfs(0, -1)
    print((dp[0][0] + dp[0][1]) % MOD)


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

N, M = map(int, input().split())
A = []
for i in range(M):
    a = int(input())
    A.append(a)
mod = 10**9 +7
dp = [0]*(N+1)
dp[0] = 1
if 1 not in A:
    dp[1]=1
for i in range(2, N+1):
    if i not in A:
        dp[i] = (dp[i-1]+dp[i-2])%mod
print(dp[-1])

### FIXED CODE ###

N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
mod = 10**9 +7
dp = [0]*(N+1)
dp[:2]= 1, 1 if 1 not in A else 0
for i in range(2, N+1):
    if i not in A:
        dp[i] = (dp[i-1]+dp[i-2])%mod
print(dp[-1])