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

# input here
_INPUT = """\
10 2
4
5
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    N, M = map(int, input().split())
    a = [int(input()) for i in range(M)]

    #動的計画法問題
    dp = [0] * (N+1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    else:
        dp[1] = 0

    for i in range(2,N+1):
        if i in a:
            continue
        dp[i] = dp[i-1] + dp[i-2]
        
        dp[i] %= (10**9+7)

    print(dp[N]) 




            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])
### BUGGY CODE ###

s = list(input())

ans = 0
flg = True
while flg:
    flg = False
    for i in range(len(s) - 1):
        if s[i] == 'B' and s[i + 1] == 'W':
            s[i] = 'W'
            s[i + 1] = 'B'
            ans += 1
            flg = True

print(ans)

### FIXED CODE ###

import sys

s = input()
first = s.find('B')

if first == -1:
    print(0)
    sys.exit()

ans = 0
for i in range(first + 1, len(s)):
    if s[i] == 'W':
        ans += i - first
        first += 1

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

def factorial(i):
    ans = 1
    for j in range(1,i+1):
        ans *= j
    return ans

N = int(input())
A = [input() for i in range(N)]
a = []
for i in A:
    b = list(i)
    b.sort()
    a.append(b)

a.sort()
ans = a[0]
count=0
for i in range(0,N):
    ans = a[i]
    for j in range(i+1,N):
        if ans == a[j]:
            count+=1
print(count)

### FIXED CODE ###

N = int(input())
A=[]
S={}
for i in range(N):
    a = list(input())
    a.sort()
    b = ''.join(a)
    if b not in S:
        S[b] = 1
    else:
        S[b] += 1


count=0
for i in S.values():
    if i==1:
        continue
    count += i*(i-1)//2
print(count)
### BUGGY CODE ###

N = int(input())
D = [int(i) for i in input().split(" ")]
count = 0
maxd = max(D)
for i in range(maxd+1):
    ARC = []
    ABC = []
    for j in D:
        if i < j:
            ARC.append(j)
        else:
            ABC.append(j)
    if len(ARC) == len(ABC):
        count+=1
print(count)

### FIXED CODE ###

N = int(input())
D = [int(i) for i in input().split(" ")]
D.sort()
print(D[int(N/2)]-D[int(N/2)-1])
### BUGGY CODE ###

n=int(input())
a=[]
b=[]
for i in range(n):
    a.append(int(input()))
next=0
count=0
while next!=1:
    if a[next]-1 in b:
        count=-1
        break
    b.append(a[next]-1)
    next=a[next]-1
    count+=1
print(count)
    


### FIXED CODE ###

n=int(input())
a = [int(input()) for _ in range(n)]
b=[]
next=0
count=0
for i in range(n):
    next=a[next]-1
    count+=1
    if next==1:
        print(count)
        exit()
print(-1)
### BUGGY CODE ###

def neighbor(N, edges):
    neighbor_list = [[] for _ in range(N)]
    for i in range(N):
        for vs in edges:
            if i + 1 in vs: # vsは頂点i+1が含まれるedge
                neighbor_list[i] += vs
        neighbor_list[i] = list(set(neighbor_list[i]))
        if i + 1 in neighbor_list[i]:
            neighbor_list[i].remove(i + 1)
        
    return neighbor_list

def neighbor2(N, nlist, edges):
    nneighbor_list = [[] for _ in range(N)]
    for i in range(N):
        nneighbor_list[i] += nlist[i]
        for e in nlist[i]:
            nneighbor_list[i] += nlist[e - 1]
        nneighbor_list[i] = list(set(nneighbor_list[i]))
        if i + 1 in nneighbor_list[i]:
            nneighbor_list[i].remove(i + 1)
    return nneighbor_list
        
        
def combination(N, K, nnlist):
    combi = 1
    clist = [False]*N
    for v in range(N):
        print(combi)
        combi *= (K - len([t for t in nnlist[v] if clist[t-1]]))
        clist[v] = True
    return combi

def paint(N, K, nlist, nnlist, clist, vlist, combi):
    vlist_next = []
    for v in vlist:
        #nnlistの中で塗られている頂点の数を数え、色候補数Kから引く
        combi *= (K - len([t for t in nnlist[v - 1] if clist[t - 1]])) 
        clist[v - 1] = True #頂点vを塗る
        vlist_next += [t for t in nlist[v - 1] if not clist[t - 1]]
    return combi, vlist_next, clist


if __name__ == '__main__':
    N, K = map(int, input().split())
    edges = [None]*(N-1)
    
    for i in range(N-1):
        edges[i] = list(map(int, input().split()))
    
    nlist = neighbor(N, edges)
    nnlist = neighbor2(N, nlist, edges)
    
    vlist_next = [1]
    combi = 1
    clist = [False]*N
    for i in range(N):
        combi, vlist_next, clist = paint(N, K, nlist, nnlist, clist=clist, vlist=vlist_next, combi=combi)
        if len(vlist_next) == 0:
            break
    
    print(combi%1000000007)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def neighbor(N, edges):
    neighbor_list = [[] for _ in range(N)]
    for a, b in edges:
        neighbor_list[a-1] += [b-1]
        neighbor_list[b-1] += [a-1]
        
    return neighbor_list


def paint(K, nlist, now_num, from_num, case_num):
        mod = 1000000007
        if  from_num == -1:
            can_use_color = K - 1
        else:
            can_use_color = K - 2
        
        if len(nlist[now_num]) - 1 > can_use_color:
            return 0
        
        for child in nlist[now_num]:
            if child == from_num:
                continue
            else:
                case_num *= can_use_color
                can_use_color -= 1
                case_num %= mod
        
        for child in nlist[now_num]:
            if child == from_num:
                continue
            else:
                case_num = paint(K, nlist, child, now_num, case_num)
        return case_num%mod
            

if __name__ == '__main__':
    N, K = map(int, input().split())
    edges = [None]*(N-1)
    
    for i in range(N-1):
        edges[i] = list(map(int, input().split()))
    
    nlist = neighbor(N, edges)


    print(paint(K, nlist, 0, -1, K))
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))

mods = list()
count = 0
mod = 1
while(True):
    mod = a[mod-1]
    count += 1
    if (mod == 2):
        print(count)
        break
    elif mod in mods:
        print(-1)
        break
    else:
        mods.append(mod)
    

### FIXED CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input())-1)
index = 0
#indexが1になったら（２ボタンを押したら）おしまい
flag = False 
count = 0
for i in range(N):
    count+=1
    index=a[index]
    if(index == 1):
        flag = True
        break
if(flag):
    print(count)
else:
    print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-


class Dice:
    def __init__(self, n):
        self.upper    = n[0]
        self.backward = n[1]
        self.right    = n[2]
        self.left     = n[3]
        self.ahead    = n[4]
        self.bottom   = n[5]

    def roll_north(self):
        self.upper, self.ahead, self.bottom, self.backward = self.backward, self.upper, self.ahead, self.bottom

    def roll_south(self):
        self.upper, self.ahead, self.bottom, self.backward = self.ahead, self.bottom, self.backward, self.upper

    def roll_east(self):
        self.upper, self.right, self.bottom, self.left = self.left, self.upper, self.right, self.bottom

    def roll_west(self):
        self.upper, self.right, self.bottom, self.left = self.right, self.bottom, self.left, self.upper
        
    def roll_side(self):
        self.ahead, self.right, self.backward, self.left = self.left, self.ahead, self.right, self.backward


dice_info = Dice(list(map(int, input().split())))
q = int(input())
upper, ahead = map(int, input().split())

for i in range(q):
    while upper != dice_info.upper or ahead != dice_info.ahead:
        dice_info.roll_north()

    while upper != dice_info.upper:
        dice_info.roll_east()

    while ahead != dice_info.ahead:
        dice_info.roll_side()

print(dice_info.right)


### FIXED CODE ###

# -*- coding: utf-8 -*-


class Dice:
    def __init__(self, n):
        self.upper    = n[0]
        self.backward = n[1]
        self.right    = n[2]
        self.left     = n[3]
        self.ahead    = n[4]
        self.bottom   = n[5]

    def roll_north(self):
        self.upper, self.ahead, self.bottom, self.backward = self.backward, self.upper, self.ahead, self.bottom

    def roll_south(self):
        self.upper, self.ahead, self.bottom, self.backward = self.ahead, self.bottom, self.backward, self.upper

    def roll_east(self):
        self.upper, self.right, self.bottom, self.left = self.left, self.upper, self.right, self.bottom

    def roll_west(self):
        self.upper, self.right, self.bottom, self.left = self.right, self.bottom, self.left, self.upper

    def roll_side(self):
        self.ahead, self.right, self.backward, self.left = self.left, self.ahead, self.right, self.backward


dice_info = Dice(list(map(int, input().split())))
q = int(input())

for i in range(q):
    upper, ahead = map(int, input().split())

    if upper is dice_info.left:
        dice_info.roll_east()
        
    elif upper is dice_info.right:
        dice_info.roll_west()

    while not (upper == dice_info.upper or ahead == dice_info.ahead):
        dice_info.roll_north()

    while upper != dice_info.upper:
        dice_info.roll_east()

    while ahead != dice_info.ahead:
        dice_info.roll_side()

    print(dice_info.left)
### BUGGY CODE ###

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

min_n = n
for i in range(n):
    tmp_n = s[:i].count('W') + s[i+1:].count('E')
    min_n = min(tmp_n, min_n)

print(min_n)

### FIXED CODE ###

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

min_n = s[1:].count('E')
tmp_n = min_n
for i in range(1, n):
    tmp_n += s[i-1].count('W') - s[i].count('E')
    min_n = min(tmp_n, min_n)

print(min_n)
### BUGGY CODE ###

from fractions import gcd
import numpy as np
N = int(input())
a = [int(c) for c in input().split()]
mod = 10**9+7
ans = a[0]
b = 0
for i in range(1, N):
  ans = ans*a[i]//gcd(ans, a[i])
a = np.array(a)
a = (ans//a)%mod
b = a.sum()
print(b%mod)

### FIXED CODE ###

import numpy as np
N = int(input())
a = np.array(input().split(), np.int64)
MOD = 10**9+7
U = 10**6+10
is_prime = np.zeros(U, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3, U, 2):
  if p*p>U:
    break
  if is_prime[p]==1:
    is_prime[p*p::p+p] = 0

M = 10**3
small_primes = np.where(is_prime[:M])[0].tolist()

B = a.copy()
lcm = 1
for p in small_primes:
  e = 0
  while np.any(a%p==0):
    a[a%p==0] //= p
    e += 1
  lcm *= p**e
  lcm %= MOD

for x in set(a.tolist()):
  lcm *= x
  lcm %= MOD

answer = sum(pow(x, MOD-2, MOD) for x in B.tolist())%MOD
answer *= lcm
answer %= MOD
print(answer)
### BUGGY CODE ###

K=int(input())
ans=-1
num=0
for i in range(K):
    num += 7*(10**i)
    if num % K == 0:
        ans = i+1
        break
print(ans)

### FIXED CODE ###

K=int(input())
ans=-1
num=0
for i in range(K):
    # num += 7*(10**i)
    # if num % K == 0:
    #ってすると計算量がやばいので
    num = (10*num+7) % K
    if num == 0:
        ans = i+1
        break
print(ans)
### BUGGY CODE ###

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

from functools import reduce
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def gcds(*numbers):
    return reduce(gcd, numbers)

ans = 0
for i in range(len(a)):
    aa = a.copy()
    aa.pop(i)
    g = gcds(*aa)
    ans = g if g > ans else ans
print(ans)

### FIXED CODE ###

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

from functools import reduce
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
"""
def gcds(*numbers):
    return reduce(gcd, numbers)
"""
l = [0 for _ in range(n)]

for i in range(1, n):
    l[i] = gcd(l[i - 1], a[i - 1])
last_gcd = 0
for i in range(n - 2, -1, -1):
    last_gcd = gcd(last_gcd, a[i + 1])
    l[i] = gcd(last_gcd, l[i])
print(max(l))
### BUGGY CODE ###

from bisect import bisect_left

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

dict_s = {}
for i, c in enumerate(s * 2):
    dict_s[c] = dict_s.get(c, []) + [i]


dict_next_i = {
    c: [dict_s[c][bisect_left(dict_s[c], i + 1)] for i in range(n)] for c in dict_s.keys()
}


def next_i(i, c):
    if c not in dict_s.keys():
        return -1
    else:
        return n * (i // n) + dict_next_i[c][i % n]


def answer():
    i = -1
    for c in t:
        i = next_i(i, c)
        if i == -1:
            return -1
    return i + 1  # 1-origin


print(answer())


### FIXED CODE ###

from bisect import bisect_left
from string import ascii_lowercase

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

dict_s = {c: [] for c in ascii_lowercase}
for i, c in enumerate(s * 2):
    dict_s[c].append(i)

for c in ascii_lowercase:
    if not dict_s[c]:
        del dict_s[c]


dict_next_i = {
    c: [dict_s[c][bisect_left(dict_s[c], i + 1)] for i in range(n)]
    for c in dict_s.keys()
}


def next_i(i, c):
    return n * (i // n) + dict_next_i[c][i % n]


def answer():
    if not all(c in s for c in t):
        return -1
    i = -1
    for c in t:
        i = next_i(i, c)
    return i + 1  # 1-origin


print(answer())
### BUGGY CODE ###

def main():
     n,m=map(int,input().split())
     field=[[] for i in range(3*n)]
     for i in range(m):
          x,y=map(int,input().split())
          x,y=x-1,y-1
          field[3*x].append(3*y+1)
          field[3*x+1].append(3*y+2)
          field[3*x+2].append(3*y)
     
     s,t=map(int,input().split())
     s,t=s-1,t-1
     s,t=3*s,3*t
     
     que=[s]
     ok=[s]
     cnt=0
     while que!=[]:
          que2=[]
          cnt+=1
          for i in que:
               for j in field[i]:
                    if j not in ok:
                         ok.append(j)
                         if j==t:
                              return cnt//3
                         que2.append(j)
          que=que2
     return -1

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

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
def main():
     n,m=map(int,input().split())
     field=[[] for i in range(3*n)]
     for i in range(m):
          x,y=map(int,input().split())
          x,y=x-1,y-1
          field[3*x].append(3*y+1)
          field[3*x+1].append(3*y+2)
          field[3*x+2].append(3*y)
     
     s,t=map(int,input().split())
     s,t=s-1,t-1
     s,t=3*s,3*t
     
     d=[float('inf') for i in range(3*n)]
     d[s]=0
     
     que=[s]
     cnt=0
     while que!=[]:
          que2=[]
          cnt+=1
          for i in que:
               for j in field[i]:
                    if d[j]>cnt:
                         d[j]=cnt
                         que2.append(j)
          que=que2
     if d[t]==float('inf'):
          print(-1)
     else:
          print(d[t]//3)
     return 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def replaceInt(N, M):
    N = abs(N-M)
    return N
    
N, M = [int(i) for i in input().split()]

if N == M :
    output = 0
elif N < M :
    if N <= M / 2:
        output = N
    else:
        output = abs(M-N)
else :
    if M == 1:
        output = 0
    else :
        output_candidates = [N]
        while True:
            N = replaceInt(N,M)
            if N in output_candidates:
                break
            output_candidates.append(N)
        output = min(output_candidates)
        
print(output)


### FIXED CODE ###

def replaceInt(N, M):
    N = abs(N-M)
    return N
    
N, M = [int(i) for i in input().split()]

if N == M :
    output = 0
elif N < M :
    if N <= M / 2:
        output = N
    else:
        output = abs(M-N)
else :
    if M == 1:
        output = 0
    else :
        N = N % M
        output_candidates = []
        while True:
            N = replaceInt(N,M)
            if N in output_candidates:
                break
            output_candidates.append(N)
        output = min(output_candidates)
        
print(output)
### BUGGY CODE ###

import copy

n = int(input())
al = [int(x) for x in input().split()]
aset = set(al)

# {number: count}
counts_d = {i: sum(j == i for j in al) for i in range(1, n + 1) if i in aset}

whole_patterns = 0
for v in counts_d.values():
    whole_patterns += int(v * (v - 1) / 2)

for a in al:
    print(whole_patterns - counts_d[a] + 1)


### FIXED CODE ###

import collections

n = input()
al = tuple(x for x in input().split())
aset = set(al)

# {number: count}
ccc = collections.Counter
counts_d = ccc(al)

# Count of count
v_counts = ccc(v for v in counts_d.values())

whole_patterns = sum(
    (int(k * (k - 1) / 2)) * v for k, v in v_counts.items() if k > 1
)

[print(whole_patterns - counts_d[a] + 1) for a in al]
### BUGGY CODE ###

import bisect
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
already = set()

def is_in(t, n):
    i = bisect.bisect_left(A, t)
    if i >= n:
        return False

    while i < n and t == A[i]:
        if i not in already:
            already.add(i)
            return True
        i += 1

    return False

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    a = A[n]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        if is_in(t - a, n):
            res += 1
            break
        t >>= 1

print(res)


### FIXED CODE ###

import bisect
import math
N = int(input())
A = list(map(int, input().split()))
T = [2 ** i for i in range(31)]
A.sort()
already = set()


def to_dic(A):
    d = {}
    for a in A:
        d[a] = d.setdefault(a, 0) + 1

    return d

def is_in(t, num):
    i = D.setdefault(t, 0)
    if i == 0:
        return 0
    s = min(i, num)
    D[t] -= s
    return s


res = 0
D = to_dic(A)
A2 = list(D.keys())
A2.sort()

for n in range(len(A2) - 1, -1, -1):
    a = A2[n]

    if a in T:
        res += D[a] // 2
        D[a] = 0

        if D[a] % 2 == 0:
            continue

    num = D[a]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        s = is_in(t - a, num)
        res += s
        num -= s
        if num == 0:
            break

        t >>= 1

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

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]

from collections import deque
N, M = mi()
x = li2(M)

dp = [[0, []] for i1 in range(N+1)]

tmp = deque([])

for i in range(M):
    dp[x[i][1]][0] = max(dp[x[i][1]][0], dp[x[i][0]][0] + 1)
    dp[x[i][0]][1].append(x[i][1])
    tmp.append(x[i][1])
    while tmp != deque():
        a = tmp.popleft()
        if dp[a][1] != []:
            for b in dp[a][1]:
                dp[b][0] = max(dp[a][0] + 1, dp[b][0])
                tmp.append(b)

#print(dp)
print(max([row[0] for row in dp])) 

### FIXED CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
N, M = mi()
x = li2(M)

#dp = dp2(0, 2, N)
dp = [[0, []] for i1 in range(N+1)]


for i in range(M):
    dp[x[i][1]][0] = max(dp[x[i][1]][0], dp[x[i][0]][0] + 1)
    dp[x[i][0]][1].append(x[i][1])
    if dp[x[i][1]][1] != []:
        for a in dp[x[i][1]][1]:
            dp[a][0] = max(dp[x[i][1]][0] + 1, dp[a][0])

print(dp)
print(max([row[0] for row in dp])) 
'''
from collections import deque
N, M = mi()
x = li2(M)

h = [0]*N
adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    h[x[i][1]] += 1
    adj[x[i][0]].append(x[i][1])

zeros = deque([])
ans = []
for i in range(N):
    if h[i] == 0:
        zeros.append(i)
        ans.append(i)

while(zeros != deque()):
    a = zeros.popleft()
    if(adj[a]):
        for b in adj[a]:
            h[b] -= 1
            if h[b] == 0:
                zeros.append(b)
                ans.append(b)

#print(ans)

dp = [0]*N
#print(ans)
#print(adj)
for a in ans:
    #print(dp)
    if adj[a]:
        for b in adj[a]:
            dp[b] = max(dp[a] + 1, dp[b])
#print(dp)
print(dp[ans[-1]])
### BUGGY CODE ###

import sys
import itertools
input = sys.stdin.readline
inf = 200000000
n, m, r = map(int, input().split())
rs = list(map(int, input().split()))
n1 = n + 1
d = [inf] * (n1 * n1)
for i in range(n1):
    d[i * n1 + i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a * n1 + b] = d[b * n1 + a] = c


def update(i, j, k):
    d[i * n1 + j] = d[j * n1 +
                      i] = min(d[i * n1 + j], d[i * n1 + k] + d[k * n1 + j])


[update(i, j, k) for k in range(1, n+1)
 for i in range(1, n+1) for j in range(i+1, n+1)]
s = inf
for q in itertools.permutations(range(r)):
    t = 0
    for i in range(r-1):
        t += d[rs[q[i]] * n1 + rs[q[i+1]]]
    if s > t:
        s = t
print(s)


### FIXED CODE ###

from itertools import product, permutations


def warshall_floyd(d):
    # d        : nxn adjacent matrix
    for k, i, j in product(range(n), repeat=3):
        if d[i][j] > d[i][k] + d[k][j]:
            d[i][j] = d[i][k] + d[k][j]


INF = float("inf")
n, m, r = map(int, input().split())
r_list = list(map(lambda x: int(x) - 1, input().split()))
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    d[a][b] = d[b][a] = c
warshall_floyd(d)

ans = float("inf")
for np in permutations(r_list):
    cand = sum([d[np[i]][np[i + 1]] for i in range(r - 1)])
    ans = min(ans, cand)

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

from collections import Counter


#nの約数列挙
def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  # sortされていない


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

a.sort()
a_max = a[-1]
div = [0]*(a_max+1)
c = Counter(a)
#print(c)
count = 0
already = []
for i in range(n):
    if c[a[i]] != 1:
        div[a[i]] = 1
        continue
    div_a = divisor(a[i])
    for j in div_a:
        if div[j] == 1:
            break
    else:
        count += 1
        div[a[i]] = 1

print(count)

### FIXED CODE ###

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

a.sort()
a_max = a[-1]
ban = [0]*(a_max+1)

count = 0
for i in range(n):
    if ban[a[i]]:
        continue
    else:
        if i == n-1 or a[i+1] != a[i]:
            count += 1
        x = a[i]
        while x <= a_max:
            ban[x] = 1
            x += a[i]
#print(ban)
print(count)
### BUGGY CODE ###

from collections import defaultdict

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

cnt = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    cnt[a].append(b)

t = []
ans = 0
for i in range(1, m+1):
    t += cnt[i]
    t.sort()
    if t: ans += t.pop()

print(ans)


### FIXED CODE ###

import heapq
from collections import defaultdict

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

cnt = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    cnt[a].append(b)

t = []
heapq.heapify(t)
ans = 0
for i in range(1, m+1):
    for j in cnt[i]:
        heapq.heappush(t, -j)
    if t: ans -= heapq.heappop(t)

print(ans)