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

import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        start=(inv2, inv2, 0)
        # 葉の場合
        if len(to[u]) == 0:
            return [deque(start)]
        # すべての子をマージ
        dpu = []
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if len(dpv) > 1:
                for d, (u0, u1, u2) in enumerate(dpv):
                    dpv[d] = (u0 + u2, u1, 0)
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()
### BUGGY CODE ###

cubes = input()

removed_cubes_count = 0

while True:
    remove_index01 = cubes.find('01')
    if remove_index01 >= 0:
        cubes = cubes[:remove_index01] + cubes[remove_index01 + 2:]
        removed_cubes_count += 2


    remove_index10 = cubes.find('10')
    if remove_index10 >= 0:
        cubes = cubes[:remove_index10] + cubes[remove_index10 + 2:]
        removed_cubes_count += 2

    if remove_index01 == -1 and remove_index10 == -1:
        break

print(removed_cubes_count)


### FIXED CODE ###

cube = input()

zero_count = 0
one_count = 0

for i in range(len(cube)):
    if cube[i] == '0':
        zero_count += 1
    else:
        one_count += 1

if zero_count < one_count:
    print(zero_count * 2)
else:
    print(one_count * 2)
### BUGGY CODE ###

import itertools
from bisect import bisect_left

N = int(input())
Lmat = [int(n) for n in input().split()]
Lmat.sort()

def iftriangle(first,second,third):
    if third < len(Lmat):
        if Lmat[first]>=Lmat[second]+Lmat[third]:
            return 0
        elif Lmat[second]>=Lmat[first]+Lmat[third]:
            return 0
        elif Lmat[third]>=Lmat[first]+Lmat[second]:
            return 0
        else:
            #print([first,second,third])
            return 1
    else:
        return 0

sum = 0
for i in range(N):
    for j in range(i+1,N):
        min_index = j
        max_index = bisect_left(Lmat, Lmat[i]+Lmat[j])
        sum+= bisect_left(Lmat, Lmat[i]+Lmat[j]) - j - 1
        """
        #print(binary_search_nearest(Lmat, Lmat[patern[0]]+Lmat[patern[1]]))#これだとjustの値しか取得できない=>bs自体を実装する必要がある)
        for Lk_index in range(min_index+1,max_index+1):
            sum += iftriangle(i,j,Lk_index)#ここは1に置き換え不可。計算が必要
        """

print(sum)

#elapsed_time = time.time() - start
#print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")



### FIXED CODE ###

import time
from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)

start = time.time()
res = 0
for i in range(n):
    for j in range(i+1,n):
        ab = l[i] + l[j]
        c_index = bisect_left(l, ab)
        res += c_index - j - 1
print(res)
### BUGGY CODE ###

import sys

H, W = map(int, input().split())
s = []
nb = 0
for _ in range(H):
    s.append(list(input()))
    nb += s[-1].count("#")

nw = H * W - nb

sy, sx = 0, 0
gy, gx = H - 1, W - 1

# たどりつけない場合
if s[gy - 1][gx] == "#" and s[gy][gx - 1] == "#":
    print(-1)
    sys.exit()

q = [[sy, sx]]
visited = [[int(1e10)]*W for _ in range(H)]
visited[sy][sx] = 0
while True:
    nq = []
    for ty, tx in q:
        if [gy, gx] in q:
            break
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ny, nx = ty + dy, tx + dx
            if 0 <= ny < H and 0 <= nx < W and s[ny][nx] == "." and visited[ny][nx] > visited[ty][tx] + 1:
                visited[ny][nx] = visited[ty][tx] + 1
                nq.append([ny, nx])
                if ny == gy and nx == gx:
                    break
    q = nq
    if [gy, gx] in q:
        temp = visited[gy][gx]
        break

print(nw - temp - 1)

### FIXED CODE ###

H, W = map(int, input().split())
s = []
nb = 0
for _ in range(H):
    s.append(list(input()))
    nb += s[-1].count("#")

nw = H * W - nb

sy, sx = 0, 0
gy, gx = H - 1, W - 1

q = [[sy, sx]]
visited = [[int(1e10)]*W for _ in range(H)]
visited[sy][sx] = 0
while q:
    ty, tx = q.pop(0)
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = ty + dy, tx + dx
        if 0 <= ny < H and 0 <= nx < W and s[ny][nx] != "#":
            if visited[ny][nx] > visited[ty][tx] + 1:
                visited[ny][nx] = visited[ty][tx] + 1
                q.append([ny, nx])
    if [gy, gx] in q:
        temp = visited[gy][gx]
        break
if visited[gy][gx] == int(1e10):
    print(-1)
else: print(nw - temp - 1)
### BUGGY CODE ###

r,b,g,n=map(int,input().split())
cnt=0
for i in range(n//r+1):
  for j in range(n//b+1):
    if r*i+b*j==n:
      cnt+=1
    elif (n-r*i-b*j)%g==0 and (n-r*i-b*j)//g>=1:
      cnt+=1
print(cnt)

### FIXED CODE ###

r,b,g,n=map(int,input().split())
cnt=0
for i in range(n//r+1):
  for j in range(n//b+1):
    if r*i+b*j==n:
      cnt+=1
    elif (n-r*i-b*j)%g==0 and (n-r*i-b*j)//g>=1:
      cnt+=1
print(cnt)
### BUGGY CODE ###

import math
N = int(input())
s = [int(input()) for _ in range(N)]
sa=s.copy()
sa.sort()
x=0
for i in s:
  if s.index(i) %2 !=sa.index(i) %2:
    x+=1
print(math.ceil(x/2))
  

### FIXED CODE ###

import numpy as np
import math
N = int(input())
s = [int(input()) for _ in range(N)]
sn=np.array(s)
sa=sn.argsort()
x=0
for i in range(N):
  if i %2 != sa[i] %2:
    x+=1
print(math.ceil(x/2))
### BUGGY CODE ###

import copy
H,W,K = map(int,input().split())
A = [list(map(int,list(input()))) for _ in range(H)]
scrmax = 0
for i in range(1,H):
    for j in range(W):
        cnt = 0
        scr = 0
        B = copy.deepcopy(A)
        B[i][j] = 0
        for k in range(i,0,-1):
            B[k][j] = B[k-1][j]
            B[k-1][j] = 0
        while True:
            flg = 0
            for i1 in range(H):
                flg1 = 0
                for m in range(W,K-1,-1):
                    for j1 in range(W-m+1):
                        if B[i1][j1]>0 and B[i1][j1:j1+m]==[B[i1][j1] for _ in range(m)]:
                            scr += 2**cnt*(B[i1][j1]*m)
                            flg = 1
                            flg1 = 1
                            B[i1][j1:j1+m] = [0 for _ in range(m)]
                            for j2 in range(j1,j1+m):
                                for k in range(i1,0,-1):
                                    B[k][j2] = B[k-1][j2]
                                    B[k-1][j2] = 0
                            break
                    if flg1==1:break
            if flg==0:break
            cnt += 1
        scrmax = max(scrmax,scr)     
print(scrmax)

### FIXED CODE ###

import copy
H,W,K = map(int,input().split())
A = [list(map(int,list(input()))) for _ in range(H)]
scrmax = 0
for i in range(1,H):
    for j in range(W):
        cnt = 0
        scr = 0
        B = copy.deepcopy(A)
        B[i][j] = 0
        for k in range(i,0,-1):
            B[k][j] = B[k-1][j]
            B[k-1][j] = 0
        while True:
            flg = 0
            for i1 in range(H):
                C = []
                while True:
                    flg1 = 0
                    cur = 0
                    m = 0
                    b = -1
                    ind = -1
                    for j1 in range(1,W):
                        if B[i1][j1]>0 and B[i1][j1]==B[i1][j1-1]:continue
                        else:
                            if B[i1][cur]>0 and j1-cur>m:
                                m = j1-cur
                                b = B[i1][cur]
                                ind = cur
                            cur = j1
                    if B[i1][cur]>0 and W-cur>m:
                        m = W-cur
                        b = B[i1][cur]
                        ind = cur
                    if m>=K:
                        flg = 1
                        flg1 = 1
                        scr += 2**cnt*b*m
                        B[i1][ind:ind+m] = [0 for _ in range(m)]
                        C.append([ind,m])
                    if flg1==0:break
                for ind,m in C:
                    for j1 in range(ind,ind+m):
                        for k in range(i1,0,-1):
                            B[k][j1] = B[k-1][j1]
                            B[k-1][j1] = 0
            if flg==0:break
            cnt += 1
        scrmax = max(scrmax,scr)     
print(scrmax)
### BUGGY CODE ###

n = int(input())
mx = 1000000000
for i in range(1,n+1):
    if n%i==0:
        ret = n//i
        if ret<=mx:
            break
print(0,0,i,0,i,ret)


### FIXED CODE ###

import math
n = int(input())
mx = 1000000000
# mx = 7
if n<mx:
    print(0, 0, 1, 0, 1, n)
else:
    mul = math.ceil((n*1.0)/mx)
    x3= mx*mul-n
    print(0,0,mx,1,x3,mul)
### BUGGY CODE ###

n, m = map(int, input().split())
A = []
for _ in range(m):
  a = int(input())
  A.append(a)

mod = 10**9 + 7
dp = [0] * (n + 1)
dp[0] = 1
if 1 not in A:
  dp[1] = 1

for i in range(2, n+1):
  if i not in A:
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod

print(dp[n])

  


### FIXED CODE ###

n, m = map(int, input().split())
A = [True] * (n+1)
for _ in range(m):
  a = int(input())
  A[a] = False

mod = 10**9 + 7
dp = [0] * (n+1)
dp[0] = 1
if A[1]:
  dp[1] = 1

for i in range(2, n+1):
  if A[i]:
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod

print(dp[n])
### BUGGY CODE ###

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

n, m = map(int, readline().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
q = int(readline())
chk = []
for i in range(q):
  V,D,C = map(int,readline().split())
  chk.append((V,D,C))
  
from collections import deque
ans = [0]*n

def bfs(s,col,d):
  global cnt
  que = deque()
  que.append((s,1,col))
  if ans[s] == 0:
    ans[s] = col
    cnt += 1
  while que:
      if cnt == n:
        break    
      now,p,col = que.popleft()
      if p > d:
        break
      for i in g[now]:
          if p <= d and ans[i] == 0:
            ans[i] = col
            cnt += 1
            if cnt == n:
              break           
          if p < d:
            que.append((i,p+1,col))

cnt = 0
for i in chk[::-1]:
  vv,d,cc = i
  bfs(vv-1,cc,d)
  if cnt == n:
    break
    
print(*ans, sep='\n')

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(4100000)
  
n,m = map(int, readline().split())
g = [[]*n for i in range(n)]
for i in range(m):
    u,v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
q = int(readline())
chk = []
for i in range(q):
  V,D,C = map(int,readline().split())
  chk.append((V,D,C))
  

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

def f(v,d,c):
  if memo[v][d] != 0:
    return
  else:
    memo[v][d] = c
    if d > 0:
      f(v,d-1,c)
      for nxt in g[v]:
        f(nxt,d-1,c)
    else:
      return

for V,D,C in chk[::-1]:
    f(V-1,D,C)

for v in range(n):
    print(memo[v][0])
### BUGGY CODE ###

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

result = 0
for i in range(N):
    flag = True
    for j in range(N):
        if i == j:
            continue
        if A[i] % A[j] == 0:
            flag = False
            break
    if flag:
        result += 1

print(result)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

sorted_A = sorted(A)
result = 0
c = Counter(sorted_A)
# 倍数を管理するテーブル
lendp = sorted_A[-1] + 1
dp = [0] * lendp

for a in sorted_A:
    dp[a] += 1
    if dp[a] == 1:
        b = a * 2
        while b < lendp:
            dp[b] += 2
            b += a

print(dp.count(1))
### BUGGY CODE ###

S = input()
cnt = 0

length = len(S)
for i in range(0,length-4):
  for j in range(i+4,length):
    if int(S[i:j+1]) % 2019 == 0:
      cnt += 1

print(cnt)

### FIXED CODE ###

import collections
S = input()
cnt = 0

mod = [0]
reverse_S = S[::-1]
for i in range(len(reverse_S)):
  now = int(reverse_S[i]) * pow(10,i,2019)
  mod.append((now + mod[i]) % 2019)


c = collections.Counter(mod)
hindo = c.values()
for i in hindo:
  if i != 1:
    cnt += i*(i-1)//2


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

def main():
    n, k = map(int, input().split())
    stones = tuple(map(int, input().split()))
    inf = 10**9
    dp = [inf]*n
    dp[0] = 0
    for i in range(n-1):
        for t in range(1, k+1):
            step = i+t
            if step < n:
                v = dp[i]+abs(stones[i]-stones[step])
                if v < dp[step]:
                    dp[step] = v
    print(dp[-1])


if __name__ == '__main__':    
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    stones = tuple(map(int, input().split()))
    inf = 10**9
    dp = [inf]*n
    dp[0] = 0
    for i in range(n):
        for t in range(1, k+1):
            step = i+t
            if step < n:
                v = dp[i]+abs(stones[i]-stones[step])
                if v < dp[step]:
                    dp[step] = v
    print(dp[-1])


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

def main():
    n=int(input())
    s=input()
    r = [0]*n
    g = [0]*n
    b = [0]*n
    ans = 0

    dict = {"R":r, "G":g, "B":b}

    for i in range(n):
        dict[s[i]][i] = 1
 
    def rgb_sum(t,i,j):
        for s3 in "RGB":
            if s3 not in t:
                if 2*j-i < n:
                    return sum(dict[s3][j+1:]) - dict[s3][2*j-i]
                else:
                    return sum(dict[s3][j+1:])
                break

    for i in range(n):
        for j in range(i,n):
            if dict[s[i]][j] == 0:                
                s1 = s[i]
                s2 = s[j]
                t = (s1,s2)
                ans += rgb_sum(t,i,j)

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n=int(input())
    s=input()
    ans = 1

    r_cnt = s.count("R")
    g_cnt = s.count("G")

    ans = r_cnt*g_cnt*(n-r_cnt-g_cnt)
 
    for i in range(n):
        for j in range(i,n):
            s1 = s[i]
            s2 = s[j]
            if s1 != s2:
                t = (s1,s2)
                for s3 in "RGB":
                    if s3 not in t:
                        if 2*j-i < n and s[2*j-i] == s3:
                            ans -= 1
                        continue

    print(ans)

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


# 最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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


X, Y = map(int, input().split())
cnt = 1
Z = lcm(X, Y)
if (X == Y) or (Y == 1):
    print(-1)
    exit()
else:
    if X < Y:
        print(X)
        exit()
    while True:
        if X * cnt > 10**18:
            print(-1)
            break
        if X*cnt % Z != 0:
            print(X*cnt)
            break
        cnt += 1




### FIXED CODE ###

X, Y = map(int, input().split())
Z = (10**18 // X) * X
if (X == Y) or (Y == 1) or (X % Y == 0):
    print(-1)
elif X < Y:
    print(X)
else:
    for i in range(Z, 0, -X):
        if i % Y != 0:
            print(i)
            break
    else:
        print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from collections import deque

N = int(input())

A = [deque(map(int, input().split())) for _ in range(N)]

ans = 0

len_count = [0]*N
lencount=0
while lencount < N:
    update = False
    done = [0]*(N)
    for i in range(N):
        if done[i] == 1: continue
        if len(A[i]) == 0: continue
        tmp = A[i][0]-1
        if done[tmp] == 1: continue
        if len(A[tmp]) !=0 and A[tmp][0]-1 == i:
            update = True
            done[i] = 1
            done[tmp] = 1
            A[i].popleft()
            A[tmp].popleft()
            if len(A[i])==0 and len_count[i]==0:
                len_count[i] = 1
                lencount+=1
            if len(A[tmp])==0 and len_count[tmp]==0:
                len_count[tmp] = 1
                lencount+=1
    #print(lencount)
    if not(update):
        print(-1)
        sys.exit()
    ans+=1
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

from collections import deque

N = int(input())
A = [deque(map(int, input().split())) for _ in range(N)]
q = []
def check(x):
    if len(A[x]) == 0: return
    tmp = A[x][0]-1
    if A[tmp][0]-1 == x:
        if tmp < x: x,tmp=tmp,x
        q.append((x,tmp))
        return

for i in range(N):
    check(i)
day = 0
while len(q) > 0:
    day+=1
    q = list(set(q))
    prevQ=[]
    prevQ,q=q,prevQ
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        A[x].popleft()
        A[y].popleft()
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        check(x)
        check(y)
    
for i in range(N):
    if len(A[i]) != 0:
        print(-1)
        sys.exit()
print(day)
### BUGGY CODE ###

def h(i):
 l=2*i;r=l+1
 if r<=H:
  if A[i]<A[l]:
   if A[l]<A[r]:A[i],A[r]=A[r],A[i];h(r)
   else:A[i],A[l]=A[l],A[i];h(l)
  elif A[i]<A[r]:A[i],A[r]=A[r],A[i];h(r)
 elif l<=H and A[i]<A[l]:A[i],A[l]=A[l],A[i];h(l)
H=0
A=[0]
for a in iter(input,'end'):
 if a[0]=='i':
  H+=1;A+=[int(a[7:])];k=H
  while k>1 and A[k//2]<A[k]:A[k],A[k//2]=A[k//2],A[k];k//=2
 else:
  print(A[1])
  if H>1:A[1]=A.pop()
  H-=1;h(1)


### FIXED CODE ###

import sys
from heapq import*
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))
### BUGGY CODE ###

n,q=[int(i) for i in input().split()]
s=input()
for i in range(q):
    l,r=[int(j) for j in input().split()]
    st=s[l-1:r]
    print(st.count("AC"))

### FIXED CODE ###

from collections import deque
n,q=map(int,input().split())
s=input()
AC=deque()
count=0
for i in range(n):
    if i!=0:
        if s[i-1:i+1]=="AC":
            count+=1
    AC.append(count)
for _ in range(q):
    l,r=map(int,input().split())
    print(AC[r-1]-AC[l-1])
### BUGGY CODE ###

from sys import stdin
import queue

H, W = [int(x) for x in stdin.readline().rstrip().split()]
A = [stdin.readline().rstrip() for _ in range(H)]
B = [[A[y][x] for x in range(W)] for y in range(H)]
q = queue.Queue()

for k in range(H):
    for l in range(W):
        if A[k][l] == '#':
            q.put((k, l, 0))

while not q.empty():
    h, w, t = q.get()
    if h > 0:
        if B[h - 1][w] == '.':
            B[h - 1][w] = '#'
            q.put((h - 1, w, t + 1))
    if h < H - 1:
        if B[h + 1][w] == '.':
            B[h + 1][w] = '#'
            q.put((h + 1, w, t + 1))
    if w > 0:
        if B[h][w - 1] == '.':
            B[h][w - 1] = '#'
            q.put((h, w - 1, t + 1))
    if w < W - 1:
        if B[h][w + 1] == '.':
            B[h][w + 1] = '#'
            q.put((h, w + 1, t + 1))
    if q.empty():
        print(t)



### FIXED CODE ###

from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
B = [list(stdin.readline().rstrip()) for _ in range(H)]

q = deque([])

for k in range(H):
    for l in range(W):
        if B[k][l] == '#':
            q.append((k, l, 0))

while len(q) > 0:
    h, w, t = q.popleft()
    if h > 0:
        if B[h - 1][w] == '.':
            B[h - 1][w] = '#'
            q.append((h - 1, w, t + 1))
    if h < H - 1:
        if B[h + 1][w] == '.':
            B[h + 1][w] = '#'
            q.append((h + 1, w, t + 1))
    if w > 0:
        if B[h][w - 1] == '.':
            B[h][w - 1] = '#'
            q.append((h, w - 1, t + 1))
    if w < W - 1:
        if B[h][w + 1] == '.':
            B[h][w + 1] = '#'
            q.append((h, w + 1, t + 1))
    if len(q) == 0:
        print(t)
### BUGGY CODE ###

N=input()
A=map(int, raw_input().split())
B=range(1,N+1)

C=[]
for x,y in zip(A,B):
	C.append(x-y)

K=set(C)
L=list(K)
L.append(0)
L.sort()

h=len(L)
l=0


ans=float("inf")

for j in range(1000):
	m=(h+l)/2
	x=L[m]
	t=0
	for y in C:
		t+=abs(-1*x+y)

	if t<ans:
		ans=t
		h=m
	else:
		l=m
	ans=min(ans,t)

print ans

### FIXED CODE ###

N=input()
A=map(int, raw_input().split())
B=range(1,N+1)
 
C=[]
for x,y in zip(A,B):
	C.append(x-y)

C.sort()

m=0
if len(C)%2==1:
	m=C[len(C)/2]
else:
	m=(C[len(C)/2-1]+C[len(C)/2])/2

	
t=0
for x in C:
	t+=abs(-1*m+x)
print t
### BUGGY CODE ###

def f(a,b,c):
        if a < b+c and b < c+a and c < a+b:
                return True
        else:
                return False

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n):
        for j in range(i+1, n):
                for k in range(j+1, n):
                        if f(l[i], l[j], l[k]) == True:
                                ans += 1
                        else:
                                break
print(ans)

### FIXED CODE ###

"""
a < b + c
b < c + a
c < a + b
↓
a < b < c && c < a+b
"""
import bisect
n = int(input())
l = list(map(int, input().split()))

ans = 0
l.sort()

for i in range(n):
    for j in range(i+1, n):
        index = bisect.bisect_left(l, l[i]+l[j], j, n)
        ans += index - j - 1
        # print(l)
        # print(l[i]+l[j])
        # print("index: "+str(index))
        # print("j: "+str(j))
        # print("index - j: "+str(index - j))
        # print("---------------")

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

n = int(input())
a = sorted([int(i) for i in input().split()])
ndiv = []
cnt = 10**6 + 1 
while a:
  flg = True
  b = a.pop(0)
  if b % cnt == 0:
    continue
  if a:
    if b % a[0] == 0:
      cnt = b
      continue
  for k in ndiv:
    if b % k == 0:
      flg = False
      break
  if flg:
    ndiv.append(b)
print(len(ndiv))

### FIXED CODE ###

import collections
n = int(input())
a = sorted([int(i) for i in input().split()])
cnt = collections.Counter(a)
max_i = a[-1] + 1
for i in a:
  if cnt[i] >= 2:
    del cnt[i]
  for j in range(i*2, max_i, i):
    del cnt[j]
print(len(cnt))