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

from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]


def solve(input_string):
    r, g, b, n = makeMultiInteger(input_string[0])
    c = 0
    nr = int(n/r)+1
    ng = int(n/g)+1
    nb = int(n/b)+1
    #print(r, g, b, n, nr, ng, nb)
    for i in range(nr):
        _sum = i*r
        if _sum > n:
            break
        for j in range(ng):
            _sum = j*g
            if _sum > n:
                break
            for k in range(nb):
                _sum = i*r + j*g + k*b
                #print(_sum)
                if _sum == n:
                    c += 1
                if _sum > n:
                    break
    return c


def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]


def solve(input_string):
    r, g, b, n = makeMultiInteger(input_string[0])
    c = 0
    nr = int(n/r)+1
    ng = int(n/g)+1
    nb = int(n/b)+1
    #print(r, g, b, n, nr, ng, nb)
    # 二分探索？
    """
    for i in range(nr):
        _sum = i*r
        if _sum == n:
            c += 1
            break
        for j in range(ng):
            _sum = j*g+i*r
            if _sum == n:
                c += 1
                break
            for k in range(nb):
                _sum = i*r + j*g + k*b
                #print(_sum)
                if _sum == n:
                    c += 1
                    break
    """
    for i in range(nr):
        _sum = i*r
        if _sum > n:
            break
        for j in range(ng):
            _sum = j*g+i*r
            if _sum > n:
                break
            rg_sum = j*g+i*r
            if (n - rg_sum) % b == 0:
                c += 1
            """
            for k in range(nb):
                _sum = i*r + j*g + k*b
                #print(_sum)
                if _sum == n:
                    c += 1
                    break
            """
    return c


def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


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

H,N = map(int,input().split())
dp = [float('INF')]*(H+1)
dp[0]=0
for _ in range(N):
    a,b = map(int,input().split())
    for i in range(1,H+1):
        dp[i]=min(dp[max(i-a,0)]+b,dp[i])

print(dp[-1])

### FIXED CODE ###

#モンスターの体力は H
#トキはN種類の魔法が使え、
#i番目の魔法を使うと、モンスターの体力を Ai減らすことができますが、
#トキの魔力を Bi消耗します。

#dp[i] = モンスターの体力を i 減らすため消耗する魔力の最小値
#dp[i+1] = min(dp[i-Ai]+Bi,dp[i])
#dp[0]=0

import numpy as np
 
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab = np.array(ab)
 
a = ab[:, 0]
b = ab[:, 1]
 
dp = np.zeros(100001, dtype=np.int)
for i in range(1, h+1):
    dp[i] = (dp[i-a]+b).min()
print(dp[h])
### BUGGY CODE ###

N, K = map(int,input().split())
h = list(map(int,input().split()))
dp = [-1]*N

def rec_dp(i,K,dp):
    minArray = []
    if i == 0:
        minArray = [0]
    for j in range(K):
        if i - (j+1) >= 0:
            stepMin = dp[i-(j+1)] + abs(h[i] - h[i-(j+1)])
            minArray.append(stepMin)
    return min(minArray)

for i in range(N):
    dp[i] = rec_dp(i,K,dp)

print(dp[N-1])

### FIXED CODE ###

N, K = map(int,input().split())
h = list(map(int,input().split()))
dp = [-1]*N
 
def rec_dp(i,K,dp):
    minArray = []
    if i == 0:
        minArray = [0]
    for j in range(K):
        if i - (j+1) >= 0:
            stepMin = dp[i-(j+1)] + abs(h[i] - h[i-(j+1)])
            minArray.append(stepMin)
    return min(minArray)
 
for i in range(N):
    dp[i] = rec_dp(i,K,dp)
 
print(dp[N-1])
### BUGGY CODE ###

#!/usr/bin/env python

n, y = map(int, input().split())
# print(n, y)

found = False
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            if 10000 * i + 5000 * j + 1000 * k == y and i + j + k == n:
                found = True
                print("{} {} {}".format(i, j, k))
                break
        if found:
            break
    if found:
        break

if not found:
    print("-1 -1 -1")


### FIXED CODE ###

#!/usr/bin/env python

n, y = map(int, input().split())
# print(n, y)

found = False
for i in range(n+1):
    for j in range(n+1):
        if i + j > n:
            break
        k = n - (i + j)
        if 10000 * i + 5000 * j + 1000 * k == y and i + j + k == n:
            found = True
            print("{} {} {}".format(i, j, k))
            break
    if found:
        break

if not found:
    print("-1 -1 -1")
### BUGGY CODE ###

from itertools import accumulate
import sys
input = sys.stdin.readline

def solve(N, X, BLUs):
    vs = [(L*B + U*(X-B), i) for i, (B, L, U) in enumerate(BLUs)]
    vs.sort(reverse=True)

    accVs = list(accumulate([0] + vs, lambda accX, X: accX + X[0]))
    D0 = -sum([L*B for B, L, U in BLUs])

    def isOK(k):
        q = k // X
        r = k % X
        accV = accVs[q+1]
        for v, i in vs[:q]:
            B, L, U = BLUs[i]
            d = D0 + accV - v
            if r <= B:
                d += L*r
            else:
                d += L*B + U*(r-B)
            if d >= 0:
                return True
        accV = accVs[q]
        for v, i in vs[q:]:
            B, L, U = BLUs[i]
            d = D0 + accV
            if r <= B:
                d += L*r
            else:
                d += L*B + U*(r-B)
            if d >= 0:
                return True
        return False

    ng, ok = -1, N*X
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    return ok


N, X = map(int, input().split())
BLUs = [tuple(map(int, input().split())) for _ in range(N)]

print(solve(N, X, BLUs))


### FIXED CODE ###

from itertools import accumulate
import sys
input = sys.stdin.readline

def solve():
    N, X = map(int, input().split())
    tests = []
    D0 = 0
    for _ in range(N):
        B, L, U = map(int, input().split())
        v = L*B + U*(X-B)
        tests.append((v, B, L, U))
        D0 -= L*B
    tests.sort(reverse=True)

    accV = 0
    accVs = [0]
    for v, B, L, U in tests:
        accV += v
        accVs.append(accV)

    def isOK(k):
        q = k // X
        r = k % X
        accV = accVs[q+1]
        for v, B, L, U in tests[:q]:
            d = D0 + accV - v
            if r <= B:
                d += L*r
            else:
                d += L*B + U*(r-B)
            if d >= 0:
                return True
        accV = accVs[q]
        for v, B, L, U in tests[q:]:
            d = D0 + accV
            if r <= B:
                d += L*r
            else:
                d += L*B + U*(r-B)
            if d >= 0:
                return True
        return False

    ng, ok = -1, N*X
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    return ok


print(solve())
### BUGGY CODE ###

n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(m)]
b=[]
for i in range(m):
  if a[i][0]==1:
    b.append(a[i][1])
x='IMPOSSIBLE'
for i in b:
  if [i,n] in a:
    x='POSSIBLE'
    break
print(x)

### FIXED CODE ###

n,m=map(int,input().split())
c=[]
d=[]
for _ in range(m):
  a,b=map(int,input().split())
  if a==1:
    c.append(b)
  elif b==n:
    d.append(a)
if len(set(c)&set(d))!=0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

N, C = list(map(int, input().split()))
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]
D0 = {}
D1 = {}
D2 = {}
for color in range(1, C + 1):
    D0[color] = 0
    D1[color] = 0
    D2[color] = 0
    
for color in range(1, C + 1):
    for i in range(N):
        for j in range(N):
            if (i + j) % 3 == 0:
                D0[color] = D0[color] + D[ c[i][j] - 1 ][ color - 1 ] 
            if (i + j) % 3 == 1:
                D1[color] = D1[color] + D[ c[i][j] - 1 ][ color - 1 ] 
            if (i + j) % 3 == 2:
                D2[color] = D2[color] + D[ c[i][j] - 1 ][ color - 1 ] 

ans = 1000000000000000
for i in range(1, C + 1):
    for j in range(1, C + 1):
        for k in range(1, C + 1):
            if i != j and j != k and k != i:
                tmp = D0[i] + D1[j] + D2[k]
                if tmp < ans:
                    ans = tmp
print(ans)


### FIXED CODE ###

N, C = list(map(int, input().split()))
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]
D0 = {}
D1 = {}
D2 = {}
for color in range(1, C + 1):
    D0[color] = 0
    D1[color] = 0
    D2[color] = 0
    
for color in range(1, C + 1):
    for i in range(N):
        for j in range(N):
            if (i + j) % 3 == 0:
                D0[color] = D0[color] + D[ c[i][j] - 1 ][ color - 1 ] 
            if (i + j) % 3 == 1:
                D1[color] = D1[color] + D[ c[i][j] - 1 ][ color - 1 ] 
            if (i + j) % 3 == 2:
                D2[color] = D2[color] + D[ c[i][j] - 1 ][ color - 1 ] 

ans = 1000000000000000
for i in range(1, C + 1):
    for j in range(1, C + 1):
        for k in range(1, C + 1):
            if i != j and j != k and k != i:
                tmp = D0[i] + D1[j] + D2[k]
                if tmp < ans:
                    ans = tmp
print(ans)
### BUGGY CODE ###

N = int(input())


def f(n):
    cnt = 0
    i = 0
    if n == 1:
        return 1
    for i in range(1, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            cnt += 2
    if (i - 1) * (i - 1) == n:
        cnt -= 1
    return cnt


ans = 0
for i in range(1, N + 1):
    ans += f(i) * i

print(ans)


### FIXED CODE ###

from math import floor
N = int(input())


def g(X):
    Y = floor(N / X)
    return Y * (Y + 1) * X // 2


ans = 0
for i in range(1, N + 1):
    ans += g(i)

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

import itertools
import heapq
N, M, R = map(int, input().split())
Visit = [int(i) for i in input().split()]
for i in range(R):
    Visit[i] -= 1
P = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    P[a-1].append((c, b-1))
    P[b-1].append((c, a-1))

def Dijk(i):
    Fin = [False for i in range(N)]
    Cost = [float("inf") for i in range(N)]
    Cost[i] = 0
    Q = [(0, i)]
    heapq.heapify(Q)
    while Q:
        cost, node = heapq.heappop(Q)
        Fin[node] = True
        for next in P[node]:
            if Fin[next[1]] == False:
                if next[0] + cost < Cost[next[1]]:
                    Cost[next[1]] = next[0] + cost
                    heapq.heappush(Q, (Cost[next[1]], next[1]))
    return Cost

E = []
for i in range(N):
    E.append(Dijk(i))

ans = float("inf")
for Order in itertools.permutations(Visit):
    temp = 0
    for i in range(R-1):
        temp += E[Order[i]][Order[i+1]]
    if temp < ans:
        ans = temp
print(ans)


### FIXED CODE ###

import itertools
import heapq
N, M, R = map(int, input().split())
Visit = [int(i) for i in input().split()]
for i in range(R):
    Visit[i] -= 1
P = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    P[a-1].append((c, b-1))
    P[b-1].append((c, a-1))

def Dijk(i):
    Fin = [False for i in range(N)]
    Cost = [float("inf") for i in range(N)]
    Cost[i] = 0
    Q = [(0, i)]
    heapq.heapify(Q)
    while Q:
        cost, node = heapq.heappop(Q)
        if Fin[node] == False:
            Fin[node] = True
            for next in P[node]:
                if Fin[next[1]] == False:
                    if next[0] + cost < Cost[next[1]]:
                        Cost[next[1]] = next[0] + cost
                        heapq.heappush(Q, (Cost[next[1]], next[1]))
    return Cost

E = []
for i in range(N):
    E.append(Dijk(i))

ans = float("inf")
for Order in itertools.permutations(Visit):
    temp = 0
    for i in range(R-1):
        temp += E[Order[i]][Order[i+1]]
    if temp < ans:
        ans = temp
print(ans)
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    n = I()
    a = LI()
    a.sort()
    ava = [0]*a[-1]

    for i in range(n):
        for j in range(n):
            if a[j]%a[i]==0 and ava[a[j]-1]<2:
                ava[a[j]-1] += 1
    print(ava.count(1))
    return
 
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys

def solve(a,n):
    m = a[-1]+1
    ava = [0]*m
    for rep in a:
        ava[rep] += 1
        if ava[rep]:
            for i in range(2*rep,m,rep):
                ava[i] += 2
    return ava.count(1)
 
if __name__=='__main__':
    n = int(sys.stdin.readline().rstrip())
    a = list(map(int,sys.stdin.readline().rstrip().split()))
    a.sort()
    print(solve(a,n))
### BUGGY CODE ###

import statistics
N = int(input())
X = list(map(int, input().split()))

for i in range(N):
  L = X[:i] + X[i+1:]
  print(statistics.median(L))

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
L = sorted(X)
left = L[N//2-1]
right = L[N//2]

for x in X:
  if x <= left:
    print(right)
  else:
    print(left)
### BUGGY CODE ###

n = int(input())
numbers = list(map(int, input().split()))
numbers = [i % 1000000007 for i in numbers]

sum = 0
for i in range(n):
    for j in range(i + 1, n):
        sum += numbers[i] * numbers[j]
        sum %= (1000000000 + 7)
print(sum)

### FIXED CODE ###

n = int(input())
numbers = list(map(int, input().split()))
result = 0
sum_of_numbers = sum(numbers)
for i in range(n - 1):
    sum_of_numbers -= numbers[i]
    result += numbers[i] * sum_of_numbers
    result %= 1000000007
print(result)
### BUGGY CODE ###

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def main():
    N, M = map(int, input().split())
    d = defaultdict(list)

    py = []
    for i in range(M):
        p, y = map(int, input().split())
        py.append((p, y))
        d[p].append(y)

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

    for p, y in py:
        x = d[p].index(y) + 1
        print(str(p).zfill(6) + str(x).zfill(6))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def main():
    N, M = map(int, input().split())
    d = defaultdict(list)

    py = []
    for i in range(M):
        p, y = map(int, input().split())
        py.append((p, y))
        d[p].append(y)

    d2 = {}
    for p in d.keys():
        d[p].sort()
        d3 = {}
        for i, y in enumerate(d[p], start=1):
            d3[y] = i
        d2[p] = d3

    for p, y in py:
        print(str(p).zfill(6) + str(d2[p][y]).zfill(6))


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

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
B = list(A)
B.sort()
m1 = B[N-1]
m2 = B[N-2]
for i in range(N):
  if A.count(m1) >= 2:
    print(m1)
  else:
    if A[i] == m1:
      print(m2)
    else:
      print(m1)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
B = list(A)
B.sort()
m1 = B[N-1]
m2 = B[N-2]
#a = A.count(m1)
for i in range(N):
  if A[i] == m1:
    print(m2)
  else:
    print(m1)
### BUGGY CODE ###

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

m=0
li=0
an=0

for i in range(n-k+1):
    if m<sum(p[i:i+k]):
        m=sum(p[i:i+k])
        li=i

for j in range(k):
    an+=(p[li+j]*0.5)+0.5

print(an)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
 
an=0
an2=0
t=0
 
for i in range(n):
    if i<k:
        an+=((p[i]+1)/2)
        an2=an
    else:
        t=((p[i-k]+1)/2)
        if an+((p[i]+1)/2)-t>an2:
            an2=an+((p[i]+1)/2)-t
        an=an+((p[i]+1)/2)-t
            
print(an2)
### BUGGY CODE ###

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

mat=[[True]*(W+2)]
queue=set()
for i in range(H):
  a_str=input()
  for j in range(W):
    if a_str[j]=="#":
      queue.add((i+1,j+1))
      
  mat.append([True]+[a=="#" for a in a_str]+[True])
  
mat.append([True]*(W+2))

#print(mat)
#print(queue)

answer=0
while(True):
  new_queue=set()
  for q in queue:
    i,j=q
    #print(q)
    if not mat[i-1][j]:
      new_queue.add((i-1,j))
      mat[i-1][j]=True
    if not mat[i+1][j]:
      new_queue.add((i+1,j))
      mat[i+1][j]=True
    if not mat[i][j-1]:
      new_queue.add((i,j-1))
      mat[i][j-1]=True
    if not mat[i][j+1]:
      new_queue.add((i,j+1))
      mat[i][j+1]=True
      
  if len(new_queue)==0:
    break
  else:
    queue=new_queue
    answer+=1
  
print(answer)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
#mark_matrix.extend([[True]+[False]*(W)+[True] for _ in range(H)])
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))
#queue = []
queue = deque()
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
#  line = input()
#  for j,ch in enumerate(line):
#    if ch == "#":
#      mark_matrix[i+1][j+1] = True
#      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)
### BUGGY CODE ###

import sys
mod = int(1e9+7)
input=sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
#S[0]は使わない
S = [[0]*60 for _ in range(N)]

tmp = A[-1]
idx = 0
while tmp > 0:
    if tmp%2:
        S[-1][idx] += 1
    idx += 1
    tmp //= 2

for i in range(N-2, 0, -1):
    for j in range(60):
        S[i][j] = S[i+1][j]
    tmp = A[i]
    idx = 0
    while tmp > 0:
        if tmp % 2:
            S[i][idx] += 1
        idx += 1
        tmp //= 2

ans = 0
for i in range(N-1):
    tmp = A[i]
    idx = 0
    while tmp > 0:
        if tmp % 2:
            ans += ((N-1-i)-S[i+1][idx])*2**idx

        else:
            ans += S[i+1][idx]*2**idx

        idx += 1
        tmp //= 2

    for x in S[i+1][idx:]:
        ans += x*2**idx%mod
        idx += 1

    ans %= mod

print(ans)

### FIXED CODE ###

mod = int(1e9+7)
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(60):
    a = 0
    b = 0
    for j in range(N):
        if A[j] % 2:
            a += 1
        else:
            b += 1
        A[j] //= 2
    ans += a*b*pow(2, i, mod)
    ans %= mod
print(ans)
### BUGGY CODE ###

N=int(input())
a_l=[int(i) for i in input().split()]

def xor(i,j):
    l=max(len(str(format(i,'b'))),len(str(format(j,'b'))))
    i2=str(format(i,'b').zfill(l))
    j2=str(format(j,'b').zfill(l))
    ans=0
    for k in range(l):
        if i2[k]!=j2[k]:
            ans+=2**(l-k-1)
    return ans

sum1=0
for i in range(N-1):
    for j in range(N-1-i):
        sum1+=xor(a_l[i],a_l[j+i+1])
print(sum1%(7+10**9))

### FIXED CODE ###

n=int(input())
lis=list(map(lambda x:format(int(x),'b'),input().split()))
l=0
for i in range(n):
    l=max(l,len(lis[i]))

d0=[0]*60
d1=[0]*60

for i in range(n):
    lis[i]=lis[i].zfill(l)
    for j in range(l):
        if lis[i][-j-1]=='0':
            d0[j]+=1
        else:
            d1[j]+=1

ans=0
for i in range(60):
    ans+=(d0[i]*d1[i]*2**i)%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import bisect

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
B_list = list(map(int, input().rstrip().split()))
C_list = list(map(int, input().rstrip().split()))
#-----

A_list.sort()
B_list.sort()
C_list.sort()

cnt=0
for i in A_list:
    ind_B = bisect.bisect_right(B_list, i) 
    for j in B_list[ind_B:]:
        ind_C = bisect.bisect_right(C_list, j)
        cnt += (N - ind_C)

print(cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
B_list = list(map(int, input().rstrip().split()))
C_list = list(map(int, input().rstrip().split()))
#-----

A_list.sort()
B_list.sort()
C_list.sort()

cnt=0
for i in B_list:
    ind_A = bisect.bisect_left(A_list, i)
    ind_C = bisect.bisect_right(C_list, i)
    cnt +=  ind_A * (N - ind_C)

print(cnt)
### BUGGY CODE ###

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

A.sort()
B=[1]*n

from math import sqrt
def eratosu():
  # if not isinstance(n,int):
  #   raise TypeError("nがint型になってねえぞ")
  # if n<2:
  #   raise ValueError('nが2よりちっちぇえぞ')
  primec = 0
  # limit = sqrt(n)
  data = A  #2,3,4,...,n
  while len(data)>0:
    p = data[0]
    # if limit <= p:
    #     return prime + data
    if len(data)>1:
        if data[1]==p:
            primec-=1
    primec+=1 
    data = [e  for e in data if e % p != 0]
  return primec 

for i in range(n):
    if i>0:
        if A[i]==A[i-1]: B[i]=0 ; B[i-1]=0 ; continue
    # if B[i]==1:
    #     for j in range(i+1,n):
    #         if A[j]%A[i]==0:
    #             B[j]=0
print(eratosu())

# print(sum(B))


### FIXED CODE ###

n=int(input())
A=sorted(list(map(int,input().split())))
B=[0]*(1+A[-1])
for i in A:
    B[i]+=1
    if B[i]==1:
        for j in range(2*i,A[-1]+1,i):
            B[j]+=1
    else:
        continue
ans=0
for i in A:
  if B[i]==1: ans+=1

print(ans)