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

import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3

memo0 = np.zeros(((n+1), (n * max(aa) + 1)), dtype=np.int64)
memo0[:] = -1
def dfs0(i, c):
    if 0 <= memo0[i, c]:
        return memo0[i, c]

    if i == len(aa):
        memo0[i, c] = 3 if total <= (2 * c) else 0
        return memo0[i][c]

    acc = 0
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c + aa[i])) % 998244353
    memo0[i, c] = acc
    return memo0[i, c]

memo1 = np.zeros(((n+1), (n * max(aa) + 1)), dtype=np.int64)
memo1[:] = -1
def dfs1(i, c):
    if 0 <= memo1[i, c]:
        return memo1[i, c]

    if i == len(aa):
        memo1[i, c] = 3 if total == (2 * c) else 0
        return memo1[i, c]

    acc = 0
    acc = (acc + dfs1(i + 1, c)) % 998244353
    acc = (acc + dfs1(i + 1, c + aa[i])) % 998244353
    memo1[i, c] = acc
    return memo1[i, c]

ret = (ret - dfs0(0, 0)) % 998244353
ret = (ret + dfs1(0, 0)) % 998244353
print(ret)

### FIXED CODE ###

import sys

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3


L = (n * max(aa) + 1)
memo = [-1] * ((n+1) * L * 2)
def dfs(i, c):
    key = (i * L * 2) + 2 * c
    if 0 <= memo[key]:
        return memo[key: key+2]

    if i == n:
        memo[key + 0] = 3 if total <= (2 * c) else 0
        memo[key + 1] = 3 if total == (2 * c) else 0
        return memo[key: key + 2]

    v0 = dfs(i + 1, c)
    v1 = dfs(i + 1, c + aa[i])

    memo[key + 0] = (2 * v0[0] + v1[0]) % 998244353
    memo[key + 1] = (v0[1] + v1[1]) % 998244353
    return memo[key: key + 2]

a, b = dfs(0, 0)
ret = (ret - a + b) % 998244353
print(ret)
### BUGGY CODE ###

import heapq
w, h = map(int, input().split())
P = [int(input()) for _ in range(w)]
Q = [int(input()) for _ in range(h)]
que = [(0, 0, 0)]
t, y, x = 0, 0, 0
seen = [[False]*(w+1) for _ in range(h+1)]
ans = 0
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
for _ in range((w+1)*(h+1)):
  while seen[y][x]:
    t, y, x = heapq.heappop(que)
  seen[y][x] = True
  ans += t
  for i in range(4):
    ny = y+dy[i]
    nx = x+dx[i]
    if 0<=ny<=h and 0<=nx<=w:
      if seen[ny][nx]:
        continue
      if dy[i]==0:
        heapq.heappush(que, (P[min(x, nx)], ny, nx))
      else:
        heapq.heappush(que, (Q[min(y, ny)], ny, nx))
print(ans)

### FIXED CODE ###

import heapq
w, h = map(int, input().split())
P = [int(input()) for _ in range(w)]
Q = [int(input()) for _ in range(h)]
heapq.heapify(P)
heapq.heapify(Q)
ans = 0
count_x, count_y = 0, 0
while P or Q:
  if not P:
    temp = heapq.heappop(Q)
    ans += temp * (w+1-count_x)
    count_y += 1
  elif not Q:
    temp = heapq.heappop(P)
    ans += temp * (h+1-count_y)
    count_x += 1
  else:
    tp, tq = P[0], Q[0]
    if tp < tq:
      temp = heapq.heappop(P)
      ans += temp * (h+1-count_y)
      count_x += 1
    else:
      temp = heapq.heappop(Q)
      ans += temp * (w+1-count_x)
      count_y += 1
print(ans)
### BUGGY CODE ###

# B - Frog 2
def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10 ** 9] * N

    dp[0] = 0
    dp[1] = abs(h[1] - h[0])
    for i in range(2, N):
        tmp = i - K
        if tmp < 0:
            tmp = 0
        for j in range(i - K, i):
            dp1 = dp[j] + abs(h[i] - h[j])
            if dp[i] >= dp1:
                dp[i] = dp1
                if dp[i] == 0:
                    break
            else:
                pass

    print(dp[N - 1])

main()

### FIXED CODE ###

#B - Frog 2
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [10 ** 9] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])

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

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

from itertools import permutations, combinations,combinations_with_replacement,product
n=int(input())
v=list(map(int, input().split()))
c=list(map(int, input().split()))
ans=0

for i in range(n+1):
    for j in combinations(range(n),i):
        x=0
        y=0
        for k in j:
            x+=v[k]
            y+=c[k]
        ans=max(ans,x-y)
print(ans)

### FIXED CODE ###

n=int(input())
v=list(map(int, input().split()))
c=list(map(int, input().split()))
ans=0

for i in range(n):
    if (v[i]>c[i]):  
        ans+=v[i]-c[i]        
 
print(ans)
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
a_set = list(set(a_list))
max_cnt = 0

for i in range(0, len(a_set)):
    cnt = a_list.count(a_set[i]) + a_list.count(a_set[i] - 1) + a_list.count(a_set[i] + 1)
    
    if cnt > max_cnt :
        max_cnt = cnt

print(max_cnt)

### FIXED CODE ###

import collections

n = int(input())
a_list = list(map(int, input().split()))
max_cnt = 0

c = collections.Counter(a_list)

for i in range(max(c.keys()) + 1) :
    cnt = c[i] + c[i + 1] + c[i + 2]
    
    if max_cnt < cnt :
        max_cnt = cnt

print(max_cnt)
### BUGGY CODE ###

n = int(input())
s = input()
passwords = []

firsts = []
firsts_seconds = [[]*10 for _ in range(10)]

for i in range(n-2):
    if len(firsts) == 10:
        break
    first =  s[i]
    if first in firsts:
        continue
    firsts.append(first)
    for j in range(i+1,n-1):
        if len(firsts_seconds[int(first)]) == 10:
            break
        second = s[j]
        first_second = first + second
        if first_second in firsts_seconds[int(first)]:
            continue
        firsts_seconds[int(first)].append(first_second)
        for k in range(j+1, n):
            password = first_second + s[k]
            if password not in passwords:
                passwords.append(password)

print(len(passwords))

### FIXED CODE ###

n = int(input())
s = input()
passwords = []

firsts = []
firsts_seconds = [[]*10 for _ in range(10)]
firsts_seconds_thirds = [[]*10 for _ in range(100)]

for i in range(n-2):
    if len(firsts) == 10:
        break
    first =  s[i]
    if first in firsts:
        continue
    firsts.append(first)
    for j in range(i+1,n-1):
        if len(firsts_seconds[int(first)]) == 10:
            break
        second = s[j]
        first_second = first + second
        if first_second in firsts_seconds[int(first)]:
            continue
        firsts_seconds[int(first)].append(first_second)
        for k in range(j+1, n):
            password = first_second + s[k]
            if password not in firsts_seconds_thirds[int(first_second)]:
                firsts_seconds_thirds[int(first_second)].append(password)
                passwords.append(password)

print(len(passwords))
### BUGGY CODE ###

from collections import deque
# 縦(H)x横(W)
H, W = map(int, input().split())
# 魔法使いの座標
CH, CW = map(int, input().split())
# ゴール
DH, DW = map(int, input().split())
# マップ
S = [list(input()) for _ in range(H)]
# 移動Aの動き方
move_a = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 移動Bの動き方
move_b = [(x, y) for x in range(-2, 3)
          for y in range(-2, 3) if (x, y) not in move_a + [(0, 0)]]

INF = 10 ** 10
# 各マスへの移動コスト
path = [[INF] * W for _ in range(H)]

q = deque()
path[CH-1][CW-1] = 0
q.append((CH-1, CW-1, 0))

while q:

    x, y, s = q.popleft()

    # 移動Aについて
    for dx, dy in move_a:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))

# 移動Bについて
    for dx, dy in move_b:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and path[nx][ny] > s+1:
            path[nx][ny] = s+1
            q.append((nx, ny, s+1))


print(path[DH-1][DW-1]) if path[DH-1][DW-1] < INF else print(-1)

### FIXED CODE ###

from collections import deque
# 縦(H)x横(W)
H, W = map(int, input().split())
# 魔法使いの座標
CH, CW = map(int, input().split())
# ゴール
DH, DW = map(int, input().split())
# マップ
S = [list(input()) for _ in range(H)]
# 移動Aの動き方
move_a = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 移動Bの動き方
move_b = [(x, y) for x in range(-2, 3)
          for y in range(-2, 3) if (x, y) not in move_a + [(0, 0)]]

INF = 10 ** 10
# 各マスへの移動コスト
path = [[INF] * W for _ in range(H)]

q = deque()
path[CH-1][CW-1] = 0
q.append((CH-1, CW-1, 0))

while q:

    x, y, s = q.popleft()

    # 移動Aについて
    for dx, dy in move_a:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))

# 移動Bについて
    for dx, dy in move_b:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and path[nx][ny] > s+1:
            path[nx][ny] = s+1
            q.append((nx, ny, s+1))


print(path[DH-1][DW-1]) if path[DH-1][DW-1] < INF else print(-1)
### BUGGY CODE ###

import math


def bfs_168(n,W):
    work_stack = []
    visited = set()
    check = [[0]]

    work_stack = check[0].copy()
    visited.add(check[0][0])
    t = 0
    result =  [math.inf] * n
    while work_stack:
        check.append([])
        for i in work_stack:
            for j, node in enumerate(W[i]):
                if node == 0:
                    continue
                if j not in visited:
                    visited.add(j)
                    check[t+1].append(j)
                    result[j] = i
        t += 1
        work_stack = check[t].copy()
    return result[1:]

def num():
    return int(input())
def nums():
    return map(int,input().split())

n,m = nums()
x = set([i for i in range(n)])
y = {i:[] for i in range(n)}

root = [list(nums()) for _ in range(m)]

W = [[0]*n  for _ in range(n)]

for i,j in root:
    W[i-1][j-1] = W[j-1][i-1] = 1

res = bfs_168(n,W)
if math.inf in res:
    print('No')
else:
    print('Yes')
    [print(i+1) for i in res]


### FIXED CODE ###

from collections import deque
import sys


readline = sys.stdin.readline
readall = sys.stdin.read
ins = lambda: readline().rstrip()
ini = lambda: int(readline().rstrip())
inm = lambda: map(int, readline().split())
inl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')


n,m = inm()
W = [[] for _ in range(n)]
for _ in range(m):
    a,b = inm()
    W[a-1].append(b-1)
    W[b-1].append(a-1)

res = [0] * n
dis = [n] * n
dis[0] = 0

q = deque()
q.append(0)
while q:
    c = q.popleft()
    for i in W[c]:
        if dis[i] > dis[c] + 1:
            dis[i] = dis[c] + 1
            res[i] = c + 1
            q.append(i)

print('Yes')
prl(res[1:])
### BUGGY CODE ###

def abc():
    n = int(input())
    p = 1
    for i in range(1, n+1):
        p *= i
    print(p % (10 ** 9 + 7))


abc()


### FIXED CODE ###

def abc():
    import math
    n = int(input())
    print(math.factorial(n) % (10 ** 9 + 7))


abc()
### BUGGY CODE ###

n = int(input())


import math
from functools import reduce
def gcd(numbers):
  return reduce (math.gcd, numbers)


res = []
a = list(map(int, input().split()))
for i in range(n):
  c = a[i]
  a.remove(c)
  res.append(gcd(a))
  a.insert(i,c)
  
ans = max(res)
print(ans)

### FIXED CODE ###

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

import math
l_gcd = []
r_gcd = []

c = a[0]
for i in a[:-1]:
  c = math.gcd(c, i)
  l_gcd.append(c)
  
c = a[-1]
for j in a[1:][::-1]:
  c = math.gcd(c, j)
  r_gcd.append(c)
  
ans = max(r_gcd[-1], l_gcd[-1])
for r, l in zip(r_gcd[:-1], l_gcd[:-1][::-1]):
  c = math.gcd(r, l)
  ans = max(ans, c)
print(ans)
### BUGGY CODE ###

X,Y = map(int,input().split())
if X == Y:
    print(-1)
    exit()
for i in range(1,10**18+1):
    a = X*i
    if a%Y != 0:
        print(a)
        exit()

### FIXED CODE ###

import math
X,Y = map(int,input().split())
a = X*Y//math.gcd(X, Y)-X
if a == 0:
    print(-1)
    exit()
print(a)
### BUGGY CODE ###

import numpy as np

N = int(input())
# P = np.array(input().split(' '), dtype = int)
P = np.array(list(map(int, input().split(' '))))

counta = 0
for i in range(N):
    counta += (min(P[:i+1]) == P[i])
print(counta)

### FIXED CODE ###

N = int(input())
# P = np.array(input().split(' '), dtype = int)
P = list(map(int, input().split(' ')))

p_min = P[0]
ans = 0
for p in P:
    if p <= p_min:
        p_min = p
        ans += 1
print(ans)
### BUGGY CODE ###

N,K = (int(i) for i in input().split())
ans=0
for a in range(1,N+1):
    for b in range(1,N+1):
        for c in range(1,N+1):
            if (a+b)%K ==0 and (b+c)%K ==0 and (c+a)%K==0:
                ans +=1
print(ans)

### FIXED CODE ###

N,K = (int(i) for i in input().split())
a=0
b=0
if K%2 !=0:
    print((N//K)**3)
else:
    for i in range (1,N+1):
        if i % K == 0:
            a += 1
        elif i % K == K/2:
            b += 1
    print(a**3+b**3)
### BUGGY CODE ###

import sys
from collections import defaultdict


read = sys.stdin.read
readline = sys.stdin.buffer.readline

INF = float('inf')


def main():
    S = input()
    L = len(S)
    d = defaultdict(int)

    for i in range(L):
        s = int(S[i:])
        a = s % 2019
        d[a] += 1

    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline

INF = float('inf')


def main():
    s = map(int, input()[::-1])
    mod = 2019
    counts = [0] * mod
    counts[0] = 1
    t = 0
    x = 1
    for num in s:
        t = (t + num * x) % mod
        counts[t] += 1
        x = (x * 10) % mod
    ans = 0
    for count in counts:
        if count > 1:
            ans += count * (count - 1) // 2
    print(ans)


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

n = 50000
c = [1 for i in range(n)]
c[0] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j <= n:
        c[j - 1] = 0
        j += i
    i += 1

while True:
    try:
        n = int(input())
        i, a, b = 0, 0, 0
        while a == 0 or b == 0:
            i += 1
            if n - i - 1 >= 0 and a == 0 and c[n - i - 1] == 1:
                a = n - i
            if n + i - 1 < 50000 and b == 0 and c[n + i - 1] == 1:
                b = n + i
        print(a,b)
    except:
        break



### FIXED CODE ###

n = 50021
c = [1 for i in range(n)]
c[0] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j <= n:
        c[j - 1] = 0
        j += i
    i += 1

while True:
    try:
        n = int(input())
        i, a, b = 0, 0, 0
        while a == 0 or b == 0:
            i += 1
            if n - i - 1 >= 0 and a == 0 and c[n - i - 1] == 1:
                a = n - i
            if n + i - 1 < 50021 and b == 0 and c[n + i - 1] == 1:
                b = n + i
        print(a,b)
    except:
        break
### BUGGY CODE ###

S = input()
 
import re
 
li = ['dream','dreamer','erase','eraser']
 
 
while len(list(S)) > 8: 
    if S[0] == 'd':
        if S[0:5] == 'dream':
            if S[5:10] == 'erase':
                S = S[5:]
            elif S[5:10] == 'dream':
                S = S[5:]
            elif S[5:7] == 'er':
                if S[7:12] == 'dream':
                    S = S[7:]
                elif S[7:12] == 'erase':
                    S = S[7:]
            else:break
 
    else:
        if S[0:6] == 'eraser':
            S = S[6:]
        elif S[0:5] == 'erase':
            if S[5:10] == 'erase':
                S = S[5:]
            elif S[5:10] == 'dream':
                S = S[5:]
        else:break
k = 0 
for l in li:
    if S == l:k = 1
if k == 0:print('NO')
else:print('YES')

### FIXED CODE ###

S = input()
li = ['dream','dreamer','erase','eraser']
li_len=[5,7,5,6]

while S:
    for i,moji in enumerate(li):
        if S[-li_len[i]:] == moji:
            S = S[:-li_len[i]]
            break
    else:
        print('NO')
        break
if not S:print('YES')
### BUGGY CODE ###

n=int(input())
c=0
while n>0:
  c+=n%10
  n//=10
print("Yes" if c%9==0 else "No")

### FIXED CODE ###

n=str(input())
s=0
for i in n:
  s+=int(i)
print("Yes" if s%9==0 else "No")
### BUGGY CODE ###

from collections import deque
N,M=list(map(int,input().split()))
AB=[set() for i in range(N+1)]
node_list=[None]*(N+1)
class node():
    def __init__(self,i):
        self.node=i
        self.prev=None
def bfs(i):#１に到達
    Done=set()
    Done.add(i)
    d=deque([i])
    child = set()
    child.add(i)
    while(d):

        kako = set()
        k=d.popleft()
        if node_list[k] is None:
            n = node(k)
        else:
            n=node_list[k]
        for i in AB[k]:
            if i not in Done:
                jk=node(i)
                jk.prev=n
                node_list[i]=jk
                Done.add(i)
                d.append(i)
                child.add(i)
                if i==1:
                    return True,jk


        node_list[k]=n
    return False,0




for i in range(M):
    A,B=list(map(int,input().split()))
    AB[A].add(B)
    AB[B].add(A)
flag1=True
for i in range(2,N+1):
    flag,jk=bfs(i)
    if flag:
        if flag1:
            print("Yes")
            flag1=False

        while(jk.prev.node!=i):
            jk=jk.prev
        print(jk.node)


### 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 ###

n=int(input())
string_list=[input() for i in range(n)]
s=set(string_list)
t=list(s)
l=[0]*len(t)
a = len(t)
for i in range(n):
  for j in range(a):
    if t[j] == string_list[i]:
      l[j]+=1
u=[]
b = max(l)
for k in range(a):
  if l[k] == b:
    u.append(t[k])
u.sort()
for x in u:
	print(x)
      
      

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]

import collections
cnt = collections.Counter(s)
dict = sorted(cnt)

max_vote = max(cnt.values())
ans = []
for a,b in cnt.items():
  if max_vote == b:
    ans.append(a)
ans = sorted(ans)
print('\n'.join(ans))
### BUGGY CODE ###

def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n-1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  # swap smaller one.
        a_list.append(a)
        b_list.append(b)
    c_list = []
    c_list = list(map(int, input().split()))
    lr_list = []
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    total = 0
    c_list = sorted(c_list, reverse=True) # Because maximum number is not selected at all.
    import itertools
    current_max = 0
    current_list = []

    c_list_new = [c_list[item-1] for item in set(a_list + b_list)]
    for new_list in itertools.permutations(c_list_new, n):
        total = 0
        for i in range(n - 1):
            total += min(new_list[a_list[i]-1], new_list[b_list[i]-1])
        if total >= current_max:
            current_max = total
            current_list = new_list

    return str(current_max) + "\n" + " ".join(map(str, current_list))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

### FIXED CODE ###


def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n - 1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  # swap smaller one.
        a_list.append(a)
        b_list.append(b)
    c_list = []
    c_list = list(map(int, input().split()))
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    edge = [[] for i in range(n)]
    for i in range(len(a_list)):
        a, b = a_list[i] - 1, b_list[i] - 1  # convert to 0 based index.
        edge[a].append(b)
        edge[b].append(a)
    c_list_new = sorted(c_list, reverse=True)

    value = sum(c_list_new[1:])

    vertices = [None] * n
    vertices[0] = c_list_new.pop(0)

    search_path = []
    search_path.extend(edge[0])

    while search_path:
        node = search_path.pop(0)
        if vertices[node] is None:
            vertices[node] = c_list_new.pop(0)
            search_path.extend(edge[node])
    return str(value) + '\n' + ' '.join(map(str, vertices))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ac = [0 for i in range(10**6+2)]

a = sorted(a)

for i in a:
    ac[i] +=1

count =0

for i in a:
    if ac[i]>0:
 
        if ac[i] == 1:
            count += 1
        for j in a:
            if j%i==0 :
                ac[j]=0


print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ac = [0 for i in range(10**6+2)]



for i in a:
    ac[i] +=1
a = sorted(set(a))
count =0

for i in a:
    if ac[i]>0:
        if ac[i] == 1:
            count += 1
        for j in range(i,10**6+2,i):
            if not ac[j]==0:
                ac[j]=0


print(count)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections


def solve(S: int):
    S = str(S)

    count = collections.defaultdict(int)
    count[0] = 1
    tmp = ''
    for s in S[::-1]:
        tmp = s + tmp
        digit = int(tmp)
        count[digit % 2019] += 1
    result = 0
    for k, v in count.items():
        result += v * (v-1) // 2
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections

def solve(S: int):
    S = list(map(int, list(str(S))))
    count = collections.defaultdict(int)

    count[0] = 1
    tmp = ''
    prev_modulo = 0
    for idx, s in enumerate(S[::-1]):
        prev_modulo = (s * pow(10, idx, 2019) + prev_modulo) % 2019
        count[prev_modulo] += 1

    result = 0
    for k, v in count.items():
        result += v * (v-1) // 2
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

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

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

### FIXED CODE ###

from math import factorial
inf = 10**9 + 7
n = int(input())
print(factorial(n)%inf)