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

w, h, n = map(int, input().split())

vec = []
for i in range(n):
    x, y, x1, y1 = map(int, input().split())
    vec.append((x, y, i))
    vec.append((x1, y1, i))

sorted_node = []

vec.sort(key=lambda x: x[1])
for p in vec:
    if p[0] == 0:
        sorted_node.append(p)
        vec.remove(p)

vec.sort(key=lambda x: x[0])
for p in vec:
    if p[1] == h:
        sorted_node.append(p)
        vec.remove(p)

vec.sort(key=lambda x: x[1], reverse=True)
for p in vec:
    if p[0] == w:
        sorted_node.append(p)
        vec.remove(p)

vec.sort(key=lambda x: x[0], reverse=True)
for p in vec:
    if p[1] == 0:
        sorted_node.append(p)
        vec.remove(p)

colors = list(map(lambda x: x[2], sorted_node))

colors = list(filter(lambda x:colors.count(x) % 2 == 0, set(colors)))

stack = []

for node in sorted_node:
    if node[2] in colors:
        if not stack or stack[-1] != node[2]:
            stack.append(node[2])
        else:
            stack.pop()

print("NO" if stack else "YES")



### FIXED CODE ###

w, h, n = map(int, input().split())

vec = []

l = []
b = []
r = []
t = []
for i in range(n):
    x, y, x1, y1 = map(int, input().split())
    c = [x, y, x1, y1]
    if( ((c[0] == 0 or c[0] == w) or (c[1] == 0 or c[1] == h)) and ((c[2] == 0 or c[2] == w) or (c[3] == 0 or c[3] == h)) ):
        if x == 0:
            l.append([x, y, i])
        elif y == 0:
            t.append([x, y, i])
        elif x == w:
            r.append([x, y, i])
        elif y == h:
            b.append([x, y, i])
        if x1 == 0:
            l.append([x1, y1, i])
        elif y1 == 0:
            t.append([x1, y1, i])
        elif x1 == w:
            r.append([x1, y1, i])
        elif y1 == h:
            b.append([x1, y1, i])

sorted_node = (
          sorted(l, key=lambda x: x[1])
        + sorted(b, key=lambda x: x[0])
        + sorted(r, key=lambda x: x[1], reverse=True)
        + sorted(t, key=lambda x: x[0], reverse=True)
        )


stack = []

for node in sorted_node:
    if not stack or stack[-1] != node[2]:
        stack.append(node[2])
    else:
        stack.pop()

print("NO" if stack else "YES")
### BUGGY CODE ###

import numpy as np

N,M = map(int,input().split(' '))
A = []
B = []

for _ in range(N):
    AB = list(map(int,input().split()))
    A.append(AB[0])
    B.append(AB[1])

Money = 0
Drink = 0
while True:
    minidx = np.argmin(A)
    Money += A[minidx]*B[minidx]
    Drink += B[minidx]
    if Drink >= M:
        Money = Money - (A[minidx]*(Drink - M))
        break
    A = np.delete(A, minidx)
    B = np.delete(B, minidx)
    
print(Money)

### FIXED CODE ###

N,M = map(int,input().split(' '))

AB = sorted(list(map(int,input().split())) for _ in range(N))
Money = 0
for A,B in AB:
    x = min(B,M)
    Money += A * x
    M -= x
print(Money)
### BUGGY CODE ###

import sys,math,itertools
import numpy as np

n=int(sys.stdin.readline())
a=np.array([sys.stdin.readline().split() for _ in range(n)],dtype='int64')

to=0
num=0

for i in itertools.permutations(range(n)):
    f=0
    num+=1
    for j in i:
        if f!=0:
            x=a[j,0]
            y=a[j,1]
            tot=((x-x0)**2+(y-y0)**2)**(1/2)
            to+=tot
            x0=x
            y0=y
        else:
            f=1
            x0=a[j,0]
            y0=a[j,1]

print(to/num)
        


### FIXED CODE ###

import sys,math,itertools
import numpy as np

n=int(sys.stdin.readline())
a=np.array([sys.stdin.readline().split() for _ in range(n)],dtype='int64')

to=0
num=0
b=np.zeros((n,n))

for i in range(n-1):
    for j in range(i+1,n):
        b[i,j]=((a[i,0]-a[j,0])**2+(a[i,1]-a[j,1])**2)**(1/2)


for i in itertools.permutations(range(n)):
    f=0
    num+=1
    for j in i:
        if f==0:
            c=j
            f=1
        else:
            if c>j:
                to+=b[j,c]
            else:
                to+=b[c,j]
            c=j


print(to/num)
### BUGGY CODE ###

import functools
n = int(input())
a_list = list(map(int,input().split()))

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if x in res or y in res:
        return y
    if x%y==0:
        return y
    else:
        while x%y!=0:
            x,y = y,x%y
        return y

res = []
tmp = []
for _ in range(n):
    e = a_list.pop(0)
    if e in tmp:
        continue
    res.append(functools.reduce(gcd, a_list))
    a_list.append(e)
    tmp.append(e)

print(max(res))

### FIXED CODE ###

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

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if y==0:
        return x
    else:
        while x%y!=0:
            x,y = y,x%y
        return y

res = []
l_gcd = [0]*(n+2)
r_gcd = [0]*(n+2)
for i in range(n+1):
    if i ==0:
        l_gcd[i] = 0
        r_gcd[n-i+1] = 0
        continue
    l_gcd[i] = gcd(l_gcd[i-1], a_list[i-1])
    r_gcd[n-i] = gcd(r_gcd[n-i+1], a_list[n-i])

for i in range(n+1):
    res.append(gcd(l_gcd[i],r_gcd[i+1]))

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

def convex(Pset):
    v1=[Pset[1][0]-Pset[0][0],Pset[1][1]-Pset[0][1]]
    v2=[Pset[2][0]-Pset[1][0],Pset[2][1]-Pset[1][1]]
    v3=[Pset[2][0]-Pset[0][0],Pset[2][1]-Pset[0][1]]
    c= v1[0]*v2[1]-v1[1]*v2[0]
    return c<=0

def area(Pset):
    v1=[Pset[1][0]-Pset[0][0],Pset[1][1]-Pset[0][1]]
    v2=[Pset[2][0]-Pset[1][0],Pset[2][1]-Pset[1][1]]
    v3=[Pset[2][0]-Pset[0][0],Pset[2][1]-Pset[0][1]]
    return abs(v1[0]*v3[1]-v1[1]*v3[0])/2.

while(1):
    n=int(raw_input())
    if n==0:        break
    P=[]
    for i in range(n):
        P.append([int(x) for x in raw_input().split()])
    ans=0
    while(len(P)>=3):
        for i in range(len(P)-2):
            Pset=P[i:i+3]
            if convex(Pset):
                ans+=area(Pset)
                del P[i+1]
                break
    print ans
    raw_input()
    

### FIXED CODE ###

def convex(Pset):
    v1=[Pset[1][0]-Pset[0][0],Pset[1][1]-Pset[0][1]]
    v2=[Pset[2][0]-Pset[1][0],Pset[2][1]-Pset[1][1]]
    v3=[Pset[2][0]-Pset[0][0],Pset[2][1]-Pset[0][1]]
    c= v1[0]*v2[1]-v1[1]*v2[0]
    return c

def area(Pset):
    v1=[Pset[1][0]-Pset[0][0],Pset[1][1]-Pset[0][1]]
    v2=[Pset[2][0]-Pset[1][0],Pset[2][1]-Pset[1][1]]
    v3=[Pset[2][0]-Pset[0][0],Pset[2][1]-Pset[0][1]]
    return abs(v1[0]*v3[1]-v1[1]*v3[0])/2.

def nopoints(Pset,P):
    v1=[Pset[1][0]-Pset[0][0],Pset[1][1]-Pset[0][1]]
    v2=[Pset[2][0]-Pset[1][0],Pset[2][1]-Pset[1][1]]
    v3=[Pset[2][0]-Pset[0][0],Pset[2][1]-Pset[0][1]]
    CPv=[ [p[0]-Pset[0][0],p[1]-Pset[0][1]] for p in P if p not in Pset]
    #print CPv
    for pv in CPv:
        rdet=1./(v1[0]*v3[1] - v1[1]*v3[0])
        t1=rdet*( v3[1]*pv[0]-v3[0]*pv[1])
        t2=rdet*(-v1[1]*pv[0]+v1[0]*pv[1])
        #print pv, v1, v3, t1,t2
        if (t1>=0 and t2>=0 and t1+t2<=1 ):
            return 0
            break
    return 1

an=1
while(1):
    n=int(raw_input())
    if n==0:        break
    P=[]
    for i in range(n):
        P.append([int(x) for x in raw_input().split()])
    ans=0
    while(len(P)>=3):
        for i in range(len(P)-2):
            Pset=P[i:i+3]
            c= convex(Pset)
            if c<=0:
                if c==0:
                    del P[i+1]
                    break
                elif nopoints(Pset,P[:]):
                    ans+=area(Pset)
                    del P[i+1]
                    break
        else:
            print 'err',P
            break
    print an, ans
    raw_input()
    an+=1
### BUGGY CODE ###

import sys


def factorial(N: int, mod: int) -> int:
    res = 1
    for i in range(1, N+1):
        res *= i
        res %= mod
    return res


N = int(input())
S = input()

if S[0] == 'W' or S[-1] == 'W':
    print(0)
    sys.exit()

op = [0]*(2*N)
op[0] = False
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        op[i] = True if op[i-1] is False else False
    else:
        op[i] = True if op[i-1] is True else False

if op.count(True) != N:
    print(0)
    sys.exit()

ans = 1
L_ct = 0
R_ct = 0
for i in op:
    if i:
        ans *= L_ct
        L_ct -= 1
    else:
        L_ct += 1
mod = 10**9+7
print(factorial(N, mod) * ans % mod)


### FIXED CODE ###

import sys
from math import factorial

N = int(input())
S = input()
mod = 10**9+7

if S[0] == 'W' or S[-1] == 'W':
    print(0)
    sys.exit()

op = "L"
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        op += 'R' if op[i-1] == 'L' else 'L'
    else:
        op += 'R' if op[i-1] == 'R' else 'L'

if op.count('L') != N:
    print(0)
    sys.exit()

ct_L, ans = 0, 1

for i in op:
    if i == 'L':
        ct_L += 1
    else:
        ans *= ct_L
        ct_L -= 1
    ans %= mod


print(factorial(N) * ans % mod)
### BUGGY CODE ###


def bscount(nums):
    """count the number of inversions (ai > aj and i < j)
    in a sequence of ints num.

    Count number of inversions using sorted list of 0..k

    >>> bscount([3, 5, 2, 1, 4])
    6
    >>> bscount([10, 2, 9, 4, 6, 5, 7, 8, 3, 1])
    29
    """
    def binsearch(li, n, e):
        i, j = 0, n-1
        while i <= j:
            mid = (i + j) // 2
            if li[mid] > e:
                j = mid - 1
            elif li[mid] < e:
                i = mid + 1
            else:
                i = mid
                break
        return i

    snums = []
    length = 0
    invs = 0

    for n in nums:
        i = binsearch(snums, length, n)
        invs += length - i
        snums.insert(i, n)
        length += 1

    return invs


def run():
    _ = int(input())  # flake8: noqa
    nums = [int(i) for i in input().split()]

    print(bscount(nums))


if __name__ == '__main__':
    run()


### FIXED CODE ###

def count(nums):
    """count the number of inversions (ai > aj and i < j)
    in a sequence of ints num.

    >>> count([3, 5, 2, 1, 4])
    6
    >>> count([10, 2, 9, 4, 6, 5, 7, 8, 3, 1])
    29
    """
    def _count(i, j):
        if i < j:
            mid = (i + j) // 2
            i1, li1 = _count(i, mid)
            i2, li2 = _count(mid+1, j)

            return _merge(li1, li2, i1 + i2)
        else:
            return (0, nums[i:i+1])

    def _merge(li1, li2, invs):
        i = j = 0
        result = []
        sums = inv = 0
        while i < len(li1) and j < len(li2):
            if li1[i] > li2[j]:
                result.append(li2[j])
                inv += 1
                j += 1
            else:
                result.append(li1[i])
                invs += sums + inv
                sums += inv
                inv = 0
                i += 1

        while i < len(li1):
            result.append(li1[i])
            invs += sums + inv
            sums += inv
            inv = 0
            i += 1
        if j < len(li2):
            result.extend(li2[j:])

        return (invs, result)

    invs, _ = _count(0, len(nums))
    return invs

def run():
    _ = int(input())  # flake8: noqa
    nums = [int(i) for i in input().split()]

    print(count(nums))


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

from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(input() for _ in range(H))
    visited_black = [[False] * W for _ in range(H)]
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                continue
            if S[h][w] == '#' and visited_black[h][w]:
                continue
            visited_white = [[False] * W for _ in range(H)]
            Q = deque([[h,w]])
            white = 0
            black = 1
            visited_black[h][w] = True
            while Q:
                i, j = Q.popleft()
                now = S[i][j]

                for n in range(4):
                    nh = i + dh[n]
                    nw = j + dw[n]

                    if not (0 <= nh < H and 0 <= nw < W):
                        continue
                    if now == '#':
                        if S[nh][nw] == '.' and (not visited_white[nh][nw]):
                            white += 1
                            visited_white[nh][nw] = True
                            Q.append([nh,nw])
                    else:
                        if S[nh][nw] == '#' and (not visited_black[nh][nw]):
                            black += 1
                            visited_black[nh][nw] = True
                            Q.append([nh,nw])
            ans += white * black

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(list(input()) for _ in range(H))
    visited = [[False] * W for _ in range(H)]
    blacks = []
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                blacks.append((h,w))

    for h, w in blacks:
        if not visited[h][w]:
            Q = deque([(h,w)])
            white = 0
            black = 1
            visited[h][w] = True
            while Q:
                i, j = Q.pop()
                now = S[i][j]

                for n in range(4):
                    nh = i + dh[n]
                    nw = j + dw[n]

                    if 0 <= nh < H and 0 <= nw < W:
                        if not visited[nh][nw]:
                            if now != S[nh][nw]:
                                visited[nh][nw] = True
                                Q.append((nh,nw))
                                if S[nh][nw] == '.':
                                    white += 1
                                else:
                                    black += 1
            ans += white * black

    print(ans)


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

s = input()
num = int(input())
t = "X"
reverse = False

for _ in range(num):
    row = input().split()
    if len(row) == 1:
        if reverse == False:
            reverse = True
        else:
            reverse = False
    else:
        if row[1] == "1":
            if reverse:
                t = t + row[2]
            else:
                t = row[2] + t
        else:
            if reverse:
                t = row[2] + t
            else:
                t = t + row[2]

if reverse:
    t = t.replace("X", s)
    print(t[::-1])
else:
    t = t.replace("X", s)
    print(t)

### FIXED CODE ###

s = input()
num = int(input())
t = "X"
reverse = False

for _ in range(num):
    row = input().split()
    if len(row) == 1:
        if reverse == False:
            reverse = True
        else:
            reverse = False
    else:
        x = row[1]
        y = row[2]
        if x == "1" and reverse:
            t += y
        elif x == "1" and not reverse:
            t = y + t
        elif x == "2" and reverse:
            t = y + t
        else:
            t += y

if reverse:
    t = t.replace("X", s)
    print(t[::-1])
else:
    t = t.replace("X", s)
    print(t)
### BUGGY CODE ###

if __name__ == "__main__":
    N = int(input())
    S = input()

    dp = [[0] * 5005 for i in range(5005)]

    for i in range(N, 0, -1):
        for j in range(N, 0, -1):
            if S[i-1] != S[j-1]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1

    result = 0
    for i in range(N):
        for j in range(N):
            if i >= j:
                continue
            now = min(dp[i][j], j-i)
            result = max(now, result)

    print(result)


### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    S = input()

    dp = [[0] * 5005 for i in range(5005)]

    for i in range(N, 0, -1):
        for j in range(N, 0, -1):
            if S[i-1] != S[j-1]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1

    result = 0
    for i in range(N):
        for j in range(N):
            if i >= j:
                continue
            now = min(dp[i][j], j-i)
            result = max([now, result])

    print(result)
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def dfs(y0, y1, x0, x1):
    global k
    m = 0
    tmp = []
    for i in range(y0, y1):
        for j in range(x0, x1):
            a[i][j] = k
            if s[i][j] == '#':
                tmp.append([i, j])
                m += 1
            if m == 2:
                break
    if m == 1:
        k -= 1
    else:
        if tmp[0][0] != tmp[1][0]:
            pos = max(tmp[0][0], tmp[1][0])
            dfs(y0, pos, x0, x1)
            dfs(pos, y1, x0, x1)
        else:
            pos = max(tmp[0][1], tmp[1][1])
            dfs(y0, y1, x0, pos)
            dfs(y0, y1, pos, x1)

h, w ,k = MAP()
s = []
a = [[0]*w for i in range(h)]
for i in range(h):
    s.append(input())

dfs(0, h, 0, w)
for i in range(h):
    print(*a[i][:])

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w, k = MAP()
s = []
p = []
q = []
for i in range(h):
    s.append(input())
    if s[i].count('#') > 0:
        p.append(i)
    else:
        q.append(i)

a = [[0]*w for i in range(h)]
num = 0
if p:
    for i in p:
        num += 1
        m = 0
        while s[i][m] == '.':
            a[i][m] = num
            m += 1
        if m < w:
            if s[i][m] == '#':
                a[i][m] = num
                m += 1
            if m < w:
                for j in range(m, w):
                    if s[i][j] == '#':
                        num += 1
                    a[i][j] = num

if q:
    for i in q:
        m = i
        while m < h and a[m][0] == 0:
            m += 1
        if m >= h:
            m = i
            while m > 0 and a[m][0] == 0:
                m -= 1
        a[i][:] = a[m][:]
for i in range(h):
    print(*a[i][:])
### BUGGY CODE ###

from collections import Counter
N=int(input())
A=list(map(int,input().split()))
l=[]
n=1
for i in A:
    l.append(i-n)
    n+=1
c=Counter(l)
c=c.most_common(N)
ans_l=[]
for i in range(len(c)):
    b=c[i][0]
    ans=0
    for j in l:
        ans+=abs(j-b)
    ans_l.append(ans)
print(min(ans_l))

### FIXED CODE ###

#from collections import Counter
import math
N=int(input())
A=list(map(int,input().split()))
l=[]
n=1
for i in A:
    l.append(i-n)
    n+=1
l.sort()
#中央値
#切り捨て
c=int(math.floor(N/2))

ans_l=[]
ans=0
for j in l:
    ans+=abs(j-l[c])

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

import re

S = input()
ans = 0
while True:
    S, n = re.subn('BW', 'WB', S)
    if n == 0:
        break
    ans += n

print(ans)

### FIXED CODE ###

S = input()

b_count = 0
ans = 0

for pos in range(len(S)):
    if S[pos] == 'B':
        b_count += 1
    else:
        ans += b_count

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

num =int(input())

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

sort_val = sorted(val)
set_val = set(sort_val)

res = True

if len(val) %2 != 0:
    for i in set_val:
        if (i == 0 and sort_val.count(i) != 1) or (i != 0 and sort_val.count(i) %2 != 0):
            res = False
            break
else:
    for i in set_val:
        if sort_val.count(0) != 0 or sort_val.count(i) %2 != 0:
            res = False
            break

cnt = 1
if res:
    for i in range(0, len(sort_val)//2):
        cnt = cnt*2 % 1000000007

print(0 if not res else cnt)


### FIXED CODE ###

num =int(input())

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

_len = len(val)
sort_val = sorted(val)
res = False

if len(sort_val) %2 == 0:
    tmp = sort_val[1::2]
    tmp2 = sort_val[::2]
    if sorted(tmp) == sorted(tmp2):
        res = True
else:
    if sort_val.count(0) != 1:
        pass
    else:
        del sort_val[0]
        tmp = sort_val[::2]
        tmp2 = sort_val[1::2]
        if sorted(tmp) == sorted(tmp2):
            res = True

cnt = 1
if res:
    for i in range(0, _len//2):
        cnt = cnt*2 % 1000000007

print(0 if not res else cnt)
### BUGGY CODE ###

nk = list(map(int, input().split()))
p = list(map(int, input().split()))
n = nk[0]
k = nk[1]
maxim = 0
for i in range(n-k+1):
    if sum(p[i:i+k]) >= maxim:
        maxim = sum(p[i:i+k])

ans = (maxim+k)/2
print(ans)

### FIXED CODE ###

def main():    
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    s = sum(p[:k])
    maxs = s
    for i in range(n-k):
        s = s - p[i] + p[i+k]
        if s > maxs:
            maxs = s
    ans = (maxs+k)/2
    print(ans)
main()
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = LI()
    A = LI()

    y = [0] * (10**6 + 1)
    z = []
    for i in A:
        y[i] += 1
        if y[i] == 1: z.append(i)


    ans = 0
    for i in A:
        if i > 1:
            if y[1] : continue
        if y[i] > 1: continue


        f = 1
        for j in z:
            if i == j: continue
            if i % j == 0 and (y[j] or y[i//j]):
                f = 0
                break

        ans += f

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

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()

    y = [0] * (10**6 + 1)
    z = [0] * (10**6 + 1)
    A = []
    for x in sys.stdin.readline().split():
        x = int(x)
        A.append(x)
        y[x] += 1
        if y[x] == 1:
            c = x * 2
            while c <= 10**6:
                z[c] = 1
                c += x

    ans = 0
    for i in range(N):
        x = A[i]
        if y[x] > 1: continue

        if z[x] == 0:
            ans += 1

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

N = int(input())
A = [int(a) for a in input().split()]

from functools import reduce
import fractions
 
mod = 10**9+7
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
num = lcm_list(A)
ans = 0
for i in A:
    ans += num//i
    ans %= mod
    
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]

mod = 10**9+7
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

t = 1
for a in A:
    t = a*t//gcd(a, t)

ans = 0
for a in A:
    ans += t//a

print(ans%mod)
### BUGGY CODE ###

import itertools
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd,numbers)
K=int(input())
ans=0
x=[]
for i in range(1,K+1):
  for j in range(1,K+1):
    x.append(math.gcd(i,j))
for i in x:
  for j in range(1,K+1):
    ans+=gcd(i,j)
print(ans)

### FIXED CODE ###

import itertools
import math
from functools import reduce
K=int(input())
ans=0
for i in range(1,K+1):
  for j in range(1,K+1):
    t=math.gcd(i,j)
    for k in range(1,K+1):
      ans+=math.gcd(t,k)
print(ans)