Harryxun/stf_run huggingface dataset:
import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [0]
b.extend(a)
b.extend([N+1])
ans = 1
for i in range(M+1):
    dan = b[i+1] - b[i]
    tori = int(1/math.sqrt(5)*(((1+math.sqrt(5))/2)**dan-((1-math.sqrt(5))/2)**dan)+0.01)
    ans *= tori
print(ans)

### FIXED CODE ###

import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]+ a+ [N+1]
fib = [0,1]
for i in range(10**5):
    fib.append((fib[-1]+fib[-2])%1000000007)
ans = 1
for i in range(len(b)-1):
    ans= (ans*fib[b[i+1]-b[i]-1])%1000000007
print(ans)
x,y = int(input().split())
 
if x*4>y and y<x*2 and y%2 == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

in_list = list(map(int, input().split()))
for i in range(5):
  if in_list[i] ==0:
    print(i+1)
s=input()
count=0
count_1=0
count_2=0
for i in range((len(s)-1)//2):
    if s[i]==s[-(i+1)]:
        count+=1
for j in range(len(s[:(len(s)+1)//2])//2):
    if s[:(len(s)+1)//2][j]==s[:(len(s)+1)//2][-(j+1)]:
        count_1+=1
for k in range(len(s[(len(s)+3)//2):])):
    if s[(len(s)+3)//2):][k]==s[(len(s)+3)//2):][-(k+1)]:
        count_2+=1
if count==(len(s)-1)//2 and count_1==len(s[:(len(s)+1)//2])//2 and count_2==len(s[(len(s)+3)//2):]):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s=input()
a=s[:len(s)//2+1//2]
b=s[len(s)//2+1:]
if s==s[::-1] and a==a[::-1] and b==b[::-1]:
    print("Yes")
else:
    print("No")
import sys
readline = sys.stdin.readline
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN

def round(f, r=0):
    return Decimal(str(f)).quantize(Decimal(str(r)), rounding=ROUND_HALF_UP)

def main():
    H, W = map(int, readline().rstrip().split())
    # 横にスライスする場合
    if H >= 3:
        ans = abs(W*(H//3) - W*(H-H//3*2))
    if W >= 3:
        ans = min(ans, abs(H*(W//3) - H*(W-W//3*2)))
    
    # 縦にスライス + 残りに横にスライス
    y1 = H
    y2 = H//2
    y3 = H - H//2
    x3 = int(round((H*W) / (H+y3)))
    x1 = W - x3
    x2 = x3
    ans = min(ans, max((x1*y1), (x2*y2), (x3*y3)) - min((x1*y1), (x2*y2), (x3*y3)))

    # 横にスライス + 残りに縦にスライス
    x1 = W
    x2 = W//2
    x3 = W - W//2
    y3 = int(round((H*W) / (W+x3)))
    y1 = H - y3
    y2 = y3
    ans = min(ans, max((x1*y1), (x2*y2), (x3*y3)) - min((x1*y1), (x2*y2), (x3*y3)))

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
from math import floor, ceil

def main():
    H, W = map(int, readline().rstrip().split())
    ans = H * W
    if H >= 3:
        ans = min(ans, abs(W*(H//3) - W*(H-H//3*2)))
    if W >= 3:
        ans = min(ans, abs(H*(W//3) - H*(W-W//3*2)))
    
    # 縦にスライス + 残りに横にスライス
    # x1_cand = [floor(W/3), ceil(W/3)]
    x1_cand = [i for i in range(1, W)]
    y1 = H
    for x1 in x1_cand:
        x2 = W - x1
        x3 = x2
        y2 = H // 2
        y3 = H - y2
        ans = min(ans, max((x1*y1), (x2*y2), (x3*y3)) - min((x1*y1), (x2*y2), (x3*y3)))

        x2 = (W-x1) // 2
        x3 = (W-x1-x2)
        ans = min(ans, max((x1*H), (x2*H), (x3*H)) - min((x1*H), (x2*H), (x3*H)))

    # 横にスライス + 残りに縦にスライス
    # y1_cand = [floor(H/3), ceil(H/3)]
    y1_cand = [i for i in range(1, H)]
    x1 = W
    for y1 in y1_cand:
        y2 = H - y1
        y3 = y2
        x2 = W // 2
        x3 = W - x2
        ans = min(ans, max((x1*y1), (x2*y2), (x3*y3)) - min((x1*y1), (x2*y2), (x3*y3)))

        y2 = (H-y1) // 2
        y3 = (H-y1-y2)
        ans = min(ans, max((W*y1), (W*y2), (W*y3)) - min((W*y1), (W*y2), (W*y3)))

    print(ans)

if __name__ == '__main__':
    main()
import sys
sys.setrecursionlimit(10**8)
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
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, K, S = mi()
A = [0]*N

if N == 1:
    print(S)
    exit()

if not S % 2:
    for i in range(K+1):
        A[i] = S//2
    for i in range(K+1, N):
        A[i] = S//2 + 1

else:
    for i in range(K+1):
        if i % 2:
            A[i] = S//2
        else:
            A[i] = S//2 + 1
    for i in range(K+1, N):
        A[i] = S//2 + 2

for i, num in enumerate(A):
    print(num, end="")
    if i != N-1:
        print(' ', end="")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
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
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, K, S = mi()
A = [0]*N

if N == 1:
    print(S)
    exit()
if K==N:
    for i in range(N):
        print(S, end="")
        if i != N-1:
            print(' ', end="")
    exit()
if S == 1:
    for i in range(K):
        print(1, end="")
        if i != N-1:
            print(' ', end="")
    for i in range(K, N):
        print(2, end="")
        if i != N-1:
            print(' ', end="")
    exit()

mod = 10**9
if not S % 2:
    for i in range(K+1):
        A[i] = S//2
    for i in range(K+1, N):
            A[i] = (S + 1) % mod + 1
else:
    for i in range(K+1):
        if i % 2:
            A[i] = S//2
        else:
            A[i] = S//2 + 1
    for i in range(K+1, N):
        A[i] = (S + 1) % mod + 1

for i, num in enumerate(A):
    print(num, end="")
    if i != N-1:
        print(' ', end="")
import numpy as np
N, K=map(int,input().split(' '))
H=np.array(list(map(int,input().split(' '))))
dp=np.zeros(N)

for i in range(N):
	if i==0:
		continue
	elif i==1:
		dp[i]=(np.abs(H[1]-H[0]))
	else:
		d = np.min(np.array([ dp[i-j]+abs(H[i]-H[i-j]) for j in range(1,K+1) if i-j>=0]))
		dp.append(d)
		
print(dp[N-1])

### FIXED CODE ###

N, K=map(int,input().split(' '))
H=list(map(int,input().split(' ')))
dp=[]

for i in range(N):
	if i==0:
		dp.append(0)
	elif i==1:
		dp.append(abs(H[1]-H[0]))
	else:
		d = min([ dp[i-j]+abs(H[i]-H[i-j]) for j in range(1,K+1) if i-j>=0])
		dp.append(d)
		
print(dp[N-1])
from math import gcd
a,b,c,d=map(int,input().split())
f=b//c - (a-1)//c
g=b//d - (a-1)//d
k=c*d//gcd(c,d)
h=f+g-(b//k-(a-1)//k)
print((b+1-a)-h)

### FIXED CODE ###

from fractions import gcd
a,b,c,d=map(int,input().split())
f=b//c - (a-1)//c
g=b//d - (a-1)//d
k=c*d//gcd(c,d)
h=f+g-(b//k-(a-1)//k)
print((b+1-a)-h)
def fraction(N):
  if N <= 1:
    return 1
  else:
    return N * fraction(N-1)
print(fraction(int(input())))


### FIXED CODE ###

def fraction(N):
  w = N
  for x in range(1, N):
    w = (w * x) % (1e9 + 7)
  return w
print("{:.0f}".format(fraction(int(input()))))
#abc100 b
d,n=map(int,input(.split()))
ans=n*100**d
print(ans)

### FIXED CODE ###

#abc100 b
d,n=map(int,input().split())

def func(x):
    if x%100!=0:
        return 0
    return func(int(x/100))+1
i=1
cnt=0
while True:
    if func(i)==d:
        cnt+=1
        if cnt==n:
            print(i)
            break
    i+=1
from collections import deque
x,y,a,b,c = map(int ,input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

p_que = deque([])
q_que = deque([])
r_que = deque([])
for i in range(a):
    p_que.append(p[i])
for i in range(b):
    q_que.append(q[i])
for i in range(c):
    r_que.append(r[i])

yamm = 0

for i in range(x):
    if p_que[0] >= r_que[0]:
        ma = int(p_que.popleft())
        yamm += ma
    else:
        ma = int(r_que.popleft())
        yamm += ma

for i in range(y):
    if q_que[0] >= r_que[0]:
        ma = int(q_que.popleft())
        yamm += ma
    else:
        ma = int(r_que.popleft())
        yamm += ma

print(yamm)

### FIXED CODE ###

x,y,a,b,c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p.sort(reverse=True)
q.sort(reverse=True)

p = p[:x]
q = q[:y]

s = p+q+r
s.sort(reverse=True)

print(sum(s[:(x+y)]))
import math

N = int(input())
A = list(map(int, input().split()))
B = 0
for i in range(N):
    B = math.gcd(B, A[i])
print(B)

### FIXED CODE ###

import fractions

N = int(input())
A = list(map(int, input().split()))
B = 0
for i in range(N):
    B = fractions.gcd(B, A[i])
print(B)
c=input().split()
for i in range(2):
    c[i]=int(c[i])
n=c[0]
m=c[1]
a=input().split()

for i in range(len(a)):
    a[i]=int(a[i])

b=[0 for i in range(m+1)]

for i in range(n-1):
    if(a[i]<a[i+1]):
        for j in range(a[i+1]-a[i]):
            b[a[i]+1+j]+=1
    else:
        for j in range(a[i+1]):
            b[j+1]+=1
        for j in range(m-a[i]):
            b[a[i]+1+j]+=1

max_value=0
max_num=0
for i in range(m):
    if(max_value<=b[i]):
        max_value=b[i]
        max_num=i

def move(x,y):
    result=0
    if(x<y):
        result=y-x
    else:
        result=(m-x)+y

    return result

sum_value=0
for i in range(n-1):
    sum_value+=min(move(max_num,a[i+1]),move(a[i],a[i+1]))
print(sum_value)

### FIXED CODE ###

n=int(input())
a=input().split()

for i in range(len(a)):
    a[i]=int(a[i])

b=[0 for i in range(len(a))]

if(n%2==0):
    for i in range(int(n/2)):
        b[i]=a[n-2*i-1]
    
    for i in range(int(n/2)):
        b[i+int(n/2)]=a[1+2*i-1]
else:
    for i in range(int((n+1)/2)):
        b[i]=a[n-2*i-1]
    for i in range(int((n-1)/2)):
        b[i+int((n+1)/2)]=a[2+2*i-1]
        
for i in range(n):
    print(b[i],end=" ")
n = int(input())
v = [int(x) for x in input().split()]

dp = [float("inf") for i in range(n+1)]
dp[0] = 0
dp[1] = abs(v[1]-v[0])
for i in range(n-1):
    dp[i+2] = min(dp[i+1]+abs(v[i+1]-v[i+2]),dp[i]+abs(v[i]-v[i+2]))

print(dp[n-1])


### FIXED CODE ###

n = int(input())
v = [int(x) for x in input().split()]

dp = [float("inf") for i in range(n+10)]
dp[0] = 0
dp[1] = abs(v[1]-v[0])
for i in range(n-2):
    dp[i+2] = min(dp[i+1]+abs(v[i+1]-v[i+2]),dp[i]+abs(v[i]-v[i+2]))

print(dp[n-1])
# -*- coding: utf-8 -*-
X,Y = map(int,input().split())
S = [X,Y]
map(hex,S)
P = S[0]
Q = S[1]
if P>Q:
  print(>)
elif P=Q:
  print(=)
else:
  print(<)

### FIXED CODE ###

X,Y = map(str,input().split())
S = [X,Y]
map(hex,S)
P = S[0]
Q = S[1]
if P>Q:
  print(">")
elif P==Q:
  print("=")
else:
  print("<")
n = int(input())
L = map(int, input().split())
print(min(L), max(L), sum(L))

### FIXED CODE ###

n = int(input())
L = list(map(int, input().split()))
print(min(L), max(L), sum(L))
n,x,m=map(int,input().split())
ans=0
p=0
l=[x]
if x%m==0:
  print(x)
else:
  for i in range(1,n):
    s=(l[i-1]**2)%m
    if s==0:
      p=1
      break
    if s in l:
      p=2
      break
    else:
      l.append(s)
  if p==2:
    t=sum(l[1:])
    k=(n-1)//(len(l)-1) #ループ何回回るか
    j=(n-1)%(len(l)-1)
    ans=x+t*k+sum(l[1:j+1])
    print(ans)
  elif p==1:
    print(sum(l))
  else:
    print(sum(l))

### FIXED CODE ###

n,x,m=map(int,input().split())
order=[-1 for i in range(m)] #-1のところにはまだ対応する余りがない、余りは高々m通り
index=0 #何番目に出た余りなのかを示す
a=[] #数列
while order[x]==-1: #ループが完成するまでは
  order[x]=index #xはindex番目の余り
  a.append(x)
  x=(x**2)%m
  index+=1
tmp=sum(a[order[x]:index]) #1ループの和、xがループの始点の余り
t=index-order[x] #1ループの長さ
if n-1<order[x]: #ループが完成しない場合
  print(sum(a[:n]))
else:
  sum1=sum(a[:order[x]]) #ループの前の和
  x1=n-order[x] #ループ部分の長さ
  n1=x1//t #ループの回数
  n2=x1%t
  print(sum1+n1*tmp+sum(a[order[x]:order[x]+n2]))
_ = input()
S = set(input().split())
_ = input()
T = set(input().spilit())
print(len(S & T))

### FIXED CODE ###

_ = input()
S = set(input().split())
_ = input()
T = set(input().split())
print(len(S & T))
n, m = map(int, input().split()) 
card = list(map(int, input().split()))
card.sort()
command = [list(map(int, input().split())) for i in range(m)]
command.sort(key=lambda x: x[1], reverse=True)

ind = 0
for i in command:
    for j in range(i[0]):
        if card[ind] > i[1]:
            break
        card[ind] = i[1]
        ind += 1
#    else:
#        continue
#    break
print(sum(card))

### FIXED CODE ###

n, m = map(int, input().split()) 
card = list(map(int, input().split()))
card.sort()
command = [list(map(int, input().split())) for i in range(m)]
command.sort(key=lambda x: x[1], reverse=True)

ind = 0
maxNum = len(card)
for i in command:
    for j in range(i[0]):
        if maxNum < ind+1:
            break
        if card[ind] >= i[1]:
            break
        card[ind] = i[1]
        ind += 1
    else:
        continue
    break
print(sum(card))
_,a,b=sorted(input())[1:];print(a*int(b))

### FIXED CODE ###

a,b=input().split()
print(min(a*int(b),b*int(a)))
na=input("")
a=int(na)
nb=input("")
b=int(nb)
c=a*b
if (c%2==0):
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

a,b = map(int,input().split())
c = a*b
if(c%2==0):
    print("Even")
elif(c%2==1):
    print("Odd")
S=input()
if S="SUN":
  print(7)
elif S="MON":
  print(6)
elif S="TUE":
  print(5)
elif S="WED":
  print(4)
elif S="THU":
  print(3)
elif S="FRI":
  print(2)
elif S="SAT":
  print(1)

### FIXED CODE ###

S=input()
if S=="SUN":
  print(7)
elif S=="MON":
  print(6)
elif S=="TUE":
  print(5)
elif S=="WED":
  print(4)
elif S=="THU":
  print(3)
elif S=="FRI":
  print(2)
elif S=="SAT":
  print(1)
# C
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

N = int(input())
divisors = make_divisors(N)
memo = 0
maX = divisors[0] + divisors[len(divisors) - 1]
for (i, r) in zip(make_divisors, reversed(make_divisors)):
    maX = min(i + r, maX)
    memo = i
    if memo == r:
        break
print(maX)


### FIXED CODE ###

# C
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

N = int(input())
divisors = make_divisors(N)
memo = 0
maX = divisors[0] + divisors[len(divisors) - 1]
for (i, r) in zip(divisors, reversed(divisors)):
    maX = min(i + r, maX)
    memo = i
    if memo == r:
        break
print(maX - 2)
n = int(input())
ans = 'No'

for i in range(1,10):
    for j in range(1,10):
        
if n == i*j:
    ans = 'Yes'
    break
    
print(ans)

### FIXED CODE ###

n = int(input())
ans = 'No'

for i in range(1,10):
    for j in range(1,10):
        if n == i*j:
            ans = 'Yes'
            break
    
print(ans)
S,W = list(map(int,input().split()))

if S =< W:
    print("unsafe")
else:
    print("safe")

### FIXED CODE ###

S,W = list(map(int,input().split()))

if S <= W:
    print("unsafe")
else:
    print("safe")
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_g

G - Longest path

"""
import collections
import functools
import sys
sys.setrecursionlimit(10000)


def get_adj_list(pairs):
    adj = collections.defaultdict(list)
    for (i, j) in pairs:
        adj[i].append(j)
    return adj


def solve(pairs):
    adj_list = get_adj_list(pairs)
    seen = set()

    @functools.lru_cache(10000)
    def dfs(u):
        seen.add(u)
        res = -1
        for v in adj_list[u]:
            if v not in seen:
                res = max(res, dfs(v))
        return 1 + res

    depths = [dfs(u) for u in range(1, N+1)]
    return max(depths)


N, M = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(M)]
res = solve(pairs)
print(res)



### FIXED CODE ###

"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_g

G - Longest path

"""
import collections
import functools
import sys
sys.setrecursionlimit(1000000)


def get_adj_list(pairs):
    adj = collections.defaultdict(list)
    for (i, j) in pairs:
        adj[i].append(j)
    return adj


def solve(pairs):
    adj_list = get_adj_list(pairs)

    @functools.lru_cache(1000000)
    def dfs(u):
        res = -1
        for v in adj_list[u]:
            res = max(res, dfs(v))
        return 1 + res

    # depths = [dfs(u) for u in range(1, N+1)]
    # print(depths)
    depths = (dfs(u) for u in range(1, N+1))
    return max(depths, default=0)


N, M = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(M)]
res = solve(pairs)
print(res)
a, b, c = map(int, inpuit().split())
print((c//a)*b)

### FIXED CODE ###

a, b, c = map(int, input().split())
print((c//a)*b)
n,a,b = [int(i) for i in input().split()]

#n is the point in which to check wheter the mark is different
def f(n,a,b):
    if n==1:
        return [a,b]

    mask = 1<<(n-1)

    #if biggest bit of a == that of b
    if a & mask == b & mask:
        v1 = f(n-1, a, b)
        v2 = f(n-1, a^mask, v1[1]^mask)
        ret = a
        ret.extend(v2)
        ret.extend(v1[1:])
        return ret        
    else:
        # biggest bit of a and b is different
        v1 = f(n-1, a, a^1)
        v2 = f(n-1, a^1^mask, b)
        v1.extend(v2)
        return v1



#exclusive or
if bin(a^b).count("1") %2==0:
    print("NO")
else:
    print("YES")
    res = f(n,a,b)
    for p in res:
        print(p, end=" ")


### FIXED CODE ###

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

#n is the point in which to check wheter the mark is different
def f(n,a,b):
    if n==1:
        return [a,b]

    mask = 1<<(n-1)

    #if biggest bit of a == that of b
    if a & mask == b & mask:
        v1 = f(n-1, a, b)
        v2 = f(n-1, a^mask, v1[1]^mask)
        ret = [a]
        ret.extend(v2)
        ret.extend(v1[1:])
        return ret        
    else:
        # biggest bit of a and b is different
        v1 = f(n-1, a, a^1)
        v2 = f(n-1, a^1^mask, b)
        v1.extend(v2)
        return v1



#exclusive or
if bin(a^b).count("1") %2==0:
    print("NO")
else:
    print("YES")
    res = f(n,a,b)
    for p in res:
        print(p, end=" ")
n, m = map(int, input().split())
list_open = []
for i in range(m):
  list_open.append(list((int(i) for i in input().split())))
dict_open = {}
for i in range(m):
  for j in range(list_open[i][0], list_open[i][1] + 1):
    try:
      dict_open[j] += 1
    else:
      dict_open[j] = 1
print(list(dict_open.values()).count(m))

### FIXED CODE ###

n, m = map(int, input().split())
min_num = 0
max_num = 10**5
           
for i in range(m):
  min_temp, max_temp = map(int, input().split())
  if min_temp > min_num:
    min_num = min_temp
  if max_temp < max_num:
    max_num = max_temp
print(max(max_num - min_num + 1, 0))
# -*- coding: utf-8 -*-
l = [] 
r = []
all_gate_clear = 0
card_count = []

#numcard
N = input()
#gatenum
M = input()
#idカードの生成
for i in range(M):
    l_temp,r_temp = map(int, input().split())
    l.append(l_temp)
    r.append(r_temp)

    
    for gate_num in range(1,M+1):
        #1ゲートの処理
        for card in range(1,N+1):
            for num in range(r[gate_num]+ 1):
                if l[gate_num] + num == card:
                    if card_count[card] == gate_num -1:
                        card_count[card] += 1
                        break

    for card in range(1,N+1):
        if card_count[card] == M:
            all_gate_clear += 1

print(all_gate_clear)

### FIXED CODE ###

# -*- coding: utf-8 -*-
l = [] 
r = []
count = 0

N, M = map(int, input().split())
l = [0] * M
r = [0] * M
for i in range(0,M):
    l[i], r[i] = map(int, input().split())

#idカードの生成
    
ml = max(l)
mr = min(r)

for i in range(1,N+1):
    if  ml <= i and i <= mr:
        count += 1

print(count)
N = int(input())
A = sorted(list(set(list(map(int, input().split())))), reverse=True)
count = 0
for i in range(N):
    for j in range(N-1, i-1, -1):
        if i != j and A[i] % A[j] == 0:
            break
        if j == i:
            count += 1
    if i == N-1 and A[N-1] in A[:N-1]:
        count -= 1
print(count)




### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)
package main

import (
	"fmt"
)

func main(){
	var w, h, x, y, r int
	fmt.Scan(&w, &h, &x, &y, &r)
	if (x + r) <= w && (x - r) >= 0 && (y + r) <= h && (y - r) >= 0{
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


### FIXED CODE ###

(W, H, x, y, r) = [int(i) for i in input().split()]
if (x-r) >= 0 and (x+r) <= W and (y-r) >= 0 and (y+r) <= H:
    print('Yes')
else:
    print('No')
H, W = map(int, input().split())
h, w = mao(int, input().split())

print(W*h + H*w -(h+w-1))

### FIXED CODE ###

H, W = map(int, input().split())
h, w = map(int, input().split())

print(H*W - W*h - H*w + h*w)
import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    S = str(input().strip())
    T = str(input().strip())

    if not set(T) <= set(S):
        return -1

    n = len(S)
    d = defaultdict(list)
    for i, s in enumerate(S, start=1):
        d[s].append(i)

    cnt = 0
    pos = 0
    for t in T:
        if pos >= d[-1]:
            cnt += 1
            pos = d[t][0]
        else:
            left = 0
            right = len(d[t])
            while left < right:
                mid = (left + right) // 2
                np = d[t][mid]
                if np <= pos:
                    left = mid + 1
                else:
                    right = mid
            pos = d[t][left]

    return n * cnt + pos


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


### FIXED CODE ###

import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    S = str(input().strip())
    T = str(input().strip())

    if not set(T) <= set(S):
        return -1

    n = len(S)
    d = defaultdict(list)
    for i, s in enumerate(S, start=1):
        d[s].append(i)

    cnt = 0
    pos = 0
    for t in T:
        if pos >= d[t][-1]:
            cnt += 1
            pos = d[t][0]
        else:
            left = 0
            right = len(d[t])
            while left < right:
                mid = (left + right) // 2
                np = d[t][mid]
                if np <= pos:
                    left = mid + 1
                else:
                    right = mid
            pos = d[t][left]

    return n * cnt + pos


if __name__ == '__main__':
    print(main())
import collections
x, n = map(int,input().split())
P = list(map(int, input().split()))
 
PX = list(map(lambda p: p-x,P))
CPX = collections.Counter(PX)
ans = 0
 
for i in range(max(max(P),x)):
  if CPX[-i] == 0:
    ans = x -i
    break
  elif CPX[i] == 0:
    ans = x +i
    break
 
print(ans)

### FIXED CODE ###

import collections
x, n= map(int, input().split())
P = list(map(int, input().split()))
 
PX = list(map(lambda p: p-x,P))
CPX = collections.Counter(PX)
ans = 0

for i in range(100):
  if CPX[-i] == 0:
    ans = x -i
    break
  elif CPX[i] == 0:
    ans = x +i
    break

print(ans)
n, q = map(int, input().split())
s = input()
t = [0] * n
for i in range(n):
    t[i + 1] = t[i] + (1 if s[i:i+2] == "AC" else 0)
for _ in range(q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])

### FIXED CODE ###

#!/usr/bin/env python3
n, q = map(int, input().split())
s = input()
t = [0] * -~n
for i in range(n):
    t[i + 1] = t[i] + (1 if s[i:i+2] == "AC" else 0)
for _ in range(q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])