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

a = int(input())
counter = 0

for n in range(1,a+1):
    for xi in range(1,n):
        for yi in range(1,n):
            for zi in range(1,n):
                if xi**2 + yi**2 + zi**2 + xi*yi + yi*zi + zi*xi == n:
                    counter += 1
                    break
    print(counter)
    counter = 0

### FIXED CODE ###

a = int(input())

x = [0] * (a+1)
for xi in range(1,101):
    for yi in range(1,101):
        for zi in range(1,101):
            result = xi**2 + yi**2 + zi**2 + xi*yi + yi*zi + zi*xi
            if result <= a:
                x[result] += 1 
for i in range(1, a+1):
    print(x[i])
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort()
accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

def isOverEq(n):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, n - a)
    return cnt >= M

overEq = -1
less = 10**18
while less - overEq > 1:
    mid = (less + overEq) // 2
    if isOverEq(mid):
        overEq = mid
    else:
        less = mid

ans = 0
cnt = 0
for a in A:
    i = bisect_left(A, overEq - a)
    ans += accA[N] - accA[i]
    ans += (N - i) * a
    cnt += N - i

ans -= max(0, cnt - M) * overEq
print(ans)


### FIXED CODE ###

from bisect import bisect_left

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

def doesOver(k):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, k - a)
    return cnt >= M

overEq = 0
less = A[-1] * 2 + 100

while less - overEq > 1:
    mid = (less + overEq) // 2
    if doesOver(mid):
        overEq = mid
    else:
        less = mid

accA = [0] * (N + 1)
for i in range(1, N + 1):
    accA[i] = accA[i - 1] + A[i - 1]

ans = 0
cnt = 0
for a in A:
    left = bisect_left(A, overEq - a)
    ans += accA[N] - accA[left]
    ans += (N - left) * a
    cnt += N - left

ans -= (cnt - M) * overEq
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

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

    n = I()
    V = []
    W = []
    for _ in range(n):
        v, w = LI()
        V.append(v)
        W.append(w)
    
    q = I()
    vl = []
    maxL = 0
    for _ in range(q):
        v, l = LI()
        maxL = max(maxL, l)
        vl.append([v,l])
    
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = V[i-1], W[i-1]
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
    
    for i in range(q):
        v, L = vl[i]
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

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

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

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

import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
b=[0]*(max(a)+1)
for i in a:
    if b[i]!=0:
        b[i]+=1
        continue
    else:
        b[i]+=1
    for j in range(2*i,max(a)+1,i):
        b[j]+=1
ans=0
for i in a:
    ans+=(1 if b[i]==1 else 0)
print(ans)


### FIXED CODE ###

import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
ma=max(a)
b=[0]*(ma+1)
a.sort()
for i in a:
    if b[i]!=0:
        b[i]+=1
        continue
    else:
        b[i]+=1
    for j in range(2*i,ma+1,i):
        b[j]+=1
ans=0
for i in a:
    if b[i]==1:
        ans+=1
print(ans)
### BUGGY CODE ###

def cmb(n, r):
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n
  
  numerator = [n - r + k + 1 for k in range(r)]
  denominator = [k + 1 for k in range(r)]
  for p in range(2,r+1):
    pivot = denominator[p - 1]
    if pivot > 1:
      offset = (n - r) % p
      for k in range(p-1,r,p):
        numerator[k - offset] /= pivot
        denominator[k] /= pivot
        
  result = 1
  for k in range(r):
    if numerator[k] > 1:
      result *= int(numerator[k])
      
  return result


N=int(input())
X=list(map(int,input().split()))
SX=sorted(X)
M=SX.pop()
MV=0
ANS=0
for x in SX:
  if (M - x) in SX:
    continue
  else:
    cb = cmb(M,x)
    if MV < cb:
      MV = cb
      ANS = x
print("{} {}".format(M,ANS))



### FIXED CODE ###

import scipy.misc

N=int(input())
X=list(map(int,input().split()))
SX=sorted(X)
M=SX.pop()
MV=10**9
ANS=0
for x in SX:
  z = abs(M - x - x)
  if MV > z:
    MV = z
    ANS = x
print("{} {}".format(M,ANS))
### BUGGY CODE ###

from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

N = input()
A = list(map(int, input().split()))
M = 10**3+1
ps = []
is_p = [True] * M
for i in range(2, M):
    if is_p[i]:
        ps.append(i)
        j = i + i
        while j < M:
            is_p[j] = False
            j += i
cnt = defaultdict(int)
for a in A:
    for p in ps:
        if a % p == 0:
            cnt[p] += 1
            while a % p == 0:
                a //= p
    if a > 1:
        cnt[a] += 1
if all([x < 2 for x in cnt.values()]):
    print("pairwise coprime")
    exit()
gcd = lambda x, y : x if y == 0 else gcd(y, x % y)
x = A[0]
for a in A[1:]:
    x = gcd(x, a)
if x == 1:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

N = input()
A = list(map(int, input().split()))
M = 10**6+1
spf = [i for i in range(M)]
for i in range(2, M):
    if spf[i] == i:
        for j in range(i+i, M, i):
            spf[j] = i
cnt = defaultdict(int)
for a in A:
    ps = set()
    while a != 1:
        ps.add(spf[a])
        a = a // spf[a]
    for p in ps:
        cnt[p] += 1
if all([x < 2 for x in cnt.values()]):
    print("pairwise coprime")
    exit()
gcd = lambda x, y : x if y == 0 else gcd(y, x % y)
x = A[0]
for a in A[1:]:
    x = gcd(x, a)
if x == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

N = int(input())
ans =0
for i in range(N-1):
  N = i+1
  
  for j in range(N):
    if N%(j+1) == 0:
      ans += 1

  
    
      
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(N-1):
    ans += (N-1)//(i+1)
    
print(ans)
### BUGGY CODE ###


ABCD = list(map(int, input().split()))

A = ABCD[0]
B = ABCD[1]
C = ABCD[2]
D = ABCD[3]

AB = B-A
count = 0

for i in range(AB+1):
    point = i+A

    if point % C == 0 or point % D == 0:
        continue
    else:
        count += 1


print(count)


### FIXED CODE ###

import fractions

ABCD = list(map(int, input().split()))

A = ABCD[0]
B = ABCD[1]
C = ABCD[2]
D = ABCD[3]


# def lcm(x, y):
#     return (x * y) // fractions.gcd(x, y)


def floor(a, b):
  # return int((a - a%b)/b)
  return a//b
def gcd(a, b):
  while b != 0:
      a, b = b, a % b
  return a
def lcm(a, b):
  return floor((a * b), gcd(a, b))

firstC = floor((A-1),C)
firstD = floor((A-1),D)
firstCD = floor((A-1),lcm(C,D))

# if A%lcm(C,D) ==0 and firstCD > 0:
#     firstCD -= 1

endC = floor(B,C)
endD = floor(B,D)
endCD = floor(B,lcm(C,D))

End = B-endC-firstD + endCD
First = (A-1) - firstC - firstD + firstCD



thereC = endC - firstC
thereD = endD - firstD
thereCD = endCD - firstCD

NoP = thereC+thereD - thereCD

# print(thereC)
# print(thereD)
# print(thereCD)
# print(NoP)
print((B-A+1)-NoP)
# print(End-First)
### BUGGY CODE ###

mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
l=[0 for i in range(60)]
for x in a:
    x=bin(x)[2:]
    col=0
    for b in x[::-1]:
        if b=='1':
            l[col] = l[col]+1
        col+=1
l2=[0 for i in range(60)]
for x in a:
    x=bin(x)[2:]
    x=x.zfill(60)
    col=0
    for b in x[::-1]:
        if b=='0':
            l2[col] = l2[col] + l[col]
        else:
            l2[col] = l2[col] + n - l[col]
        col+=1
cnt=0
c=1
for i in range(60):
    cnt+=l2[i]*c
    c*=2
    c%=mod
print(cnt//2%mod)

### FIXED CODE ###

mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
l=[0 for i in range(60)]
for x in a:
    x=bin(x)[2:]
    col=0
    for b in x[::-1]:
        if b=='1':
            l[col] = l[col]+1
        col+=1
l2=[0 for i in range(60)]
for x in a:
    x=bin(x)[2:]
    x=x.zfill(60)
    col=0
    for b in x[::-1]:
        if b=='0':
            l2[col] = l2[col] + l[col]
        else:
            l2[col] = l2[col] + n - l[col]
        col+=1
cnt=0
c=1
for i in range(60):
    cnt+=l2[i]*c
    c*=2
    c%=mod
print(cnt//2%mod)
### BUGGY CODE ###

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

count = 0
for i in range(0,N,1):
    for j in range(i+1,N,1):
        for k in range(j+1,N,1):
            if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]  and abs(k-j) != abs(j-i):
                count +=1

print(count)


### FIXED CODE ###

N = int(input())
S =input()
r = S.count('R')
b = S.count('B')
g = S.count('G')
x = r*b*g

count = 0
for i in range(0,N,1):
    for j in range(i+1,N,1):
        if 2*j-i > len(S)-1:
            continue
        if S[i] != S[j] and S[j] != S[2*j-i] and S[i] != S[2*j-i]:
            count +=1

print(x-count)
### BUGGY CODE ###

# pypy
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import defaultdict
import gc

R, C, K = map(int, readline().split())
rcv = list(map(int, read().split()))
rr = rcv[::3]
cc = rcv[1::3]
vv = rcv[2::3]
rc2v = defaultdict(int)
for _r, _c, _v in zip(rr, cc, vv):
    rc2v[(_r-1, _c-1)] = _v

del rcv, rr, cc, vv
gc.collect()


dp = [[[0]*4 for c in range(C)] for r in range(R)]
dp[0][0][1] = rc2v[(0, 0)]

for c in range(1, C):
    for k in range(1, 4):
        dp[0][c][k] = max(dp[0][c-1][k], dp[0][c-1][k-1]+rc2v[(0, c)])

for r in range(1, R):
    dp[r][0][0] = max(dp[r-1][0])
    if (r, 0) in rc2v:
        dp[r][0][1] = max(dp[r-1][0]) + rc2v[(r, 0)]

for r in range(1, R):
    for c in range(1, C):
        dp[r][c][0] = max(dp[r][c-1][0], max(dp[r-1][c]))
        for k in range(1, 4):
            dp[r][c][k] = max(dp[r][c-1][k], dp[r][c-1][k-1] + rc2v[(r, c)])
            
        dp[r][c][1] = max(dp[r][c][1], max(dp[r-1][c]) + rc2v[(r, c)])

print(max(dp[-1][-1]))

### FIXED CODE ###

# pypy
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

R, C, K = map(int, readline().split())
rcv = list(map(int, read().split()))
rc2v = {}
for rr, cc, vv in zip(rcv[::3], rcv[1::3], rcv[2::3]):
    rc2v[(rr-1, cc-1)] = vv

dp = [[[0]*4 for c in range(C)] for r in range(2)]
dp[0][0][1] = rc2v[(0, 0)] if (0, 0) in rc2v else 0

for c in range(1, C):
  for k in range(1, 4):
    v = rc2v[(0, c)] if (0, c) in rc2v else 0
    dp[0][c][k] = max(dp[0][c-1][k], dp[0][c-1][k-1]+v)

for r in range(1, R):
  rr = r % 2
  dp[rr][0][0] = max(dp[rr-1][0])
  v = rc2v[(r, 0)] if (r, 0) in rc2v else 0
  dp[rr][0][1] = dp[rr][0][0] + v
  for c in range(1, C):
    v = rc2v[(r, c)] if (r, c) in rc2v else 0
    temp_max = max(dp[rr-1][c])
    dp[rr][c][1] = max(dp[rr][c-1][1], max(dp[rr][c-1][0], temp_max)+v)
    for k in range(2, 4):
      dp[rr][c][k] = max(dp[rr][c-1][k], dp[rr][c-1][k-1]+v)
    
if R % 2:
  print(max(dp[0][-1]))
else:
  print(max(dp[-1][-1]))
### BUGGY CODE ###

import itertools 
 
n=int(input())
 
L=list(map(int,input().split()))
cnt=0
for v in itertools.combinations(L,3):
    v=list(v)
    v.sort()
    if v[0]+v[1]>v[2]:
        cnt+=1
print(cnt)

### FIXED CODE ###

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

L.sort()
cnt=0
for i in range(n-2):
    for j in range(i+1,n-1):
        if L[i]+L[j]<=L[j+1]:
            continue
        if L[i]+L[j]>L[n-1]:
            cnt+=n-j-1
            continue
        left=j+1
        right=n-1
        while right-left>1:
            mid=left+(right-left)//2
            if L[mid]<L[i]+L[j]:
                left=mid
            else:
                right=mid
        cnt+=left-j
print(cnt)
### BUGGY CODE ###

N = int(input())
List = list(map(int, input().split()))

count = 'YES'
for i in range(N-1):
    for j in range(N-1-i):
        if List[i] == List[i+1+j]:
            count = 'NO'

print(count)

### FIXED CODE ###

N = int(input())
List = list(map(int, input().split()))

List.sort()
count = 'YES'
for i in range(N-1):
    if List[i] == List[i+1]:
        count = 'NO'
        
print(count)
### BUGGY CODE ###

k = int(input())
s = input()
mod = 10**9+7

def cmb(n, r, p):
    assert n < p, 'n is less than modp'
    assert n < max_n, 'n in less than max_n'
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

modp = mod
max_n = k + len(s)+1          # 必要分だけ用意する
fact = [1, 1] + [0]*max_n     # fact[n] = (n! mod modp)
factinv = [1, 1] + [0]*max_n  # factinv[n] = ((n!)^(-1) mod modp)
inv = [0, 1] + [0]*max_n      # factinv 計算用


for i in range(2, max_n + 1):
    fact[i] = (fact[i-1] * i) % modp
    inv[i] = (-inv[modp % i] * (modp // i)) % modp
    factinv[i] = (factinv[i-1] * inv[i]) % modp

ans = 0
for i in range(k+1):
    now = pow(26, k-i, mod)
    now = (now * pow(25, i, mod))%mod
    now = (now * cmb(i+len(s)-1, len(s)-1, mod))%mod
    ans += now
print(ans%mod)

### FIXED CODE ###

k = int(input())
s = input()
mod = 10**9+7

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

modp = mod
max_n = k + len(s)+1 # 必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod modp)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod modp)
inv = [0, 1]  # factinv 計算用

for i in range(2, max_n + 1):
    fact.append((fact[-1] * i) % modp)
    inv.append((-inv[modp % i] * (modp // i)) % modp)
    factinv.append((factinv[-1] * inv[-1]) % modp)

ans = 0
for i in range(k+1):
    now = pow(26, k-i, mod)
    now = (now * pow(25, i, mod))%mod
    now = (now * cmb(i+len(s)-1, len(s)-1, mod))%mod
    ans += now
print(ans%mod)
### BUGGY CODE ###

def g(j,i):
  a=B[j-1][i-1]
  b1=B[j-1]
  m=[]
  for y in range(j,n+1):
    b=B[y]
    m.append(max([b[x]+a-b[i-1]-b1[x] for x in range(i,n+1)]))
  return max(m)
n=int(raw_input())
N=range(n)
B=[[0]*(n+1) for _ in range(n+1)]
for j in N:
  A=map(int,raw_input().split())
  s=0
  b=B[j]
  for i in N:
    s+=A[i]
    B[j+1][i+1]=b[i+1]+s
N=N[1:]+[n]
m=[max([g(j,i) for i in N]) for j in N]
print max(m)

### FIXED CODE ###

def f(m,b):
  s=0
  for k in N[j:]:
    s+=A[k]
    b[k]=max(b[k],0)+s
    m=max(b[k],m)
  return m,b

m=-1e9
n=int(raw_input())
N=range(n)
B=[[0]*(n+1) for _ in range(n+1)]
for _ in N:
  A=map(int,raw_input().split())
  for j in N: m,B[j]=f(m,B[j])
print m
### BUGGY CODE ###

# -*- coding: utf_8 -*-

from itertools import repeat
from itertools import combinations

def rec(s, i, total, m):
    if total == m:
        return 1

    if len(s) == i or total > m:
        return 0

    return rec(s, i + 1, total, m) + rec(s, i + 1, total + s[i], m)

def loop(s, m):
    for i in range(len(s)):
        comb = list(combinations(s, i))
        for c in comb:
            if sum(c) == m:
                return 1

    return 0

if __name__ == "__main__":
    n = int(input())
    a = [int (x) for x in input().split()]
    q = int(input())
    m = [int (x) for x in input().split()]
    for i in m:
        #print("yes") if rec(a, 0, 0, i) > 0 else print("no")
        print("yes") if loop(a, i) > 0 else print("no")

### FIXED CODE ###

# -*- coding: utf_8 -*-

from itertools import repeat
from itertools import combinations

def rec(s, i, total, m):
    if total == m:
        return 1

    if len(s) == i or total > m:
        return 0

    return rec(s, i + 1, total, m) + rec(s, i + 1, total + s[i], m)


def makeCache(s):
    cache = {}
    for i in range(len(s)):
        comb = list(combinations(s, i))
        for c in comb:
            cache[sum(c)] = 1

    return cache

def loop(s, m):
    for i in range(len(s)):
        comb = list(combinations(s, i))
        for c in comb:
            if sum(c) == m:
                return 1

    return 0

if __name__ == "__main__":
    n = int(input())
    a = [int (x) for x in input().split()]
    q = int(input())
    m = [int (x) for x in input().split()]
    s = makeCache(a)
    for i in m:
        #print("yes") if rec(a, 0, 0, i) > 0 else print("no")
        #print("yes") if loop(a, i) > 0 else print("no")
        print("yes") if i in s else print("no")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
  V[a].add(b)
  V[b].add(a)
#print(V)
maxc = 0
for v in V:
  maxc = max(maxc,len(v))
#print(maxc)
CM = set(range(1,maxc+1))
CE = {}
for e in E:
  CE[e] = 0
#print(CE)

def dfs(u,t,c):
  CU = set()
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
    CU.add(c)
  #for v in V[u]:
  #  if CE[(min(u,v),max(u,v))] != 0:
  #    CU.add(CE[(min(u,v),max(u,v))])
  CC = CM-CU
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      dfs(v,u,CC.pop())

dfs(1,0,1)
print(maxc)
for e in E:
  print(CE[e])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
  V[a].add(b)
  V[b].add(a)
#print(V)
maxc = 0
for v in V:
  maxc = max(maxc,len(v))
#print(maxc)
CE = {}
for e in E:
  CE[e] = 0
#print(CE)

def dfs(u,t,c):
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
  cc = c+1
  if cc > maxc:
    cc = 1
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      dfs(v,u,cc)
      cc += 1
      if cc > maxc:
        cc = 1

dfs(1,0,1)
print(maxc)
for e in E:
  print(CE[e])
### BUGGY CODE ###

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

if N == 1:
  print(1)
  exit(0)
#
A.sort()
A.append(0) 

b = []
ans = 0
i = 0
while i < N:
  c = A[i]
  for j in b:
    if c % j == 0:
      break
  else:
    b.append(c)
    if c != A[i+1]:
      ans += 1
  while c == A[i+1]:
    i += 1
  i += 1
#          
print(ans)


### FIXED CODE ###

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

cnt = [0] * 1000001

for i in A:
  if cnt[i] == 1:
    continue 
  if cnt[i] == 2:
    cnt[i] = 1
    continue
  cnt[i] = 2
  for j in range( (i+i),1000001,i):
    cnt[j] = 1
#
ans = 0
for i in range(1000001):
  if cnt[i] == 2:
    ans += 1
#
print(ans)
### BUGGY CODE ###

from sys import stdin
from functools import lru_cache


# 最小化問題
def chmin(a,b):
    if a > b: return b
    else: return a


class Rec_memo:
    def __init__(self, N, h_arr):
        self.dp = [float('inf')] * (N+2)
        self.h_arr = h_arr

    def rec(self, i):
        if self.dp[i] != float('inf'):
            return self.dp[i]
        elif i == 0:
            return 0
        else:
            try:
                self.dp[i] = chmin(self.dp[i],self.rec(i-1)+abs(self.h_arr[i]-self.h_arr[i-1]))
            except:
                pass
            if i>1:
                self.dp[i] = chmin(self.dp[i],self.rec(i-2)+abs(self.h_arr[i]-self.h_arr[i-2]))
            return self.dp[i]



if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    h_arr = [0] * (N+2)
    h_arr[0:N] = list(map(int,_in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    # dp[i]:=カエルが足場iへと移動するのに必要な最小コスト
    dp = [float('inf')] * (N+2)  # 最小化問題
    dp[0] = 0                    # 初期条件
    
    # 貰うDP
    #for i in range(0,N):
    #    dp[i] = chmin(dp[i],dp[i-1]+abs(h_arr[i]-h_arr[i-1]))
    #    if i > 1:
    #        dp[i] = chmin(dp[i],dp[i-2]+abs(h_arr[i]-h_arr[i-2]))
    #cnt = dp[N-1]

    # 配るDP
    #for i in range(0,N):
    #    dp[i+1] = chmin(dp[i+1],dp[i]+abs(h_arr[i]-h_arr[i+1]))
    #    dp[i+2] = chmin(dp[i+2],dp[i]+abs(h_arr[i]-h_arr[i+2]))
    #cnt = dp[N-1]

    # メモ化再帰
    memo = Rec_memo(N,h_arr)
    cnt = memo.rec(N-1)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


### FIXED CODE ###

from sys import stdin


# 最小化問題
def chmin(a,b):
    if a > b: return b
    else: return a


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    h_arr = list(map(int,_in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dp = [float('inf')] * N  # 最小化問題
    dp[0] = 0                # 初期条件
    
    for i in range(0,N):
        dp[i] = chmin(dp[i],dp[i-1]+abs(h_arr[i]-h_arr[i-1]))
        if i > 1:
            dp[i] = chmin(dp[i],dp[i-2]+abs(h_arr[i]-h_arr[i-2]))
    cnt = dp[N-1]
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)
### BUGGY CODE ###

import re
n,q=map(int,input().split())
s=input()

for i in range(q):
    l,r=[int(i)-1 for i in input().split()]
    string=s[l:r+1]
    ans=re.findall("AC",string)
    print(len(ans))

### FIXED CODE ###

import re
n,q=map(int,input().split())
s=input()

a=[0]*(n+1)
for i in range(1,n+1):
    # print(s[i-1:i+1])
    if s[i-1:i+1]=="AC":
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]

for i in range(q):
    l,r=[int(i) for i in input().split()]
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

def prime(n):
    num=[i for i in range(n,1,-1)]
    prime=[]
    p = 2
    while p <=n**0.5 and len(num) != 0:
        p=num.pop()
        prime.append(p)
        num = [i for i in num if i%p != 0 and n%i == 0]
    return prime
def chk_prime(n):
    for i in range(2,-1*int(-n**0.5//1)):
        if n%i == 0:
            return False
    return True

def main():
    a,b=map(int,input().split(' '))

    ans = 1
    if chk_prime(min(a,b)):
        if max(a,b)%min(a,b) == 0 and min(a,b) != 1:
            ans = 2
    else:
        prime_list=prime(int(min(a,b)/2))
        for i in prime_list:
            if a%i == 0 and b%i==0:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from math import *
def gcd(n,m):
    while m != 0:
        n,m=m,n%m
    return n
def main():
    a,b=map(int,input().split(' '))
    g=gcd(a,b)
    cnt = 1
    g2 = int(sqrt(g))
    for i in range(2,g2+1):
        if g%i ==0:
            while g%i ==0:
                g //= i
            cnt += 1
    if g > 1:
        cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()