Harryxun/stf_run huggingface dataset:
N=int(input())
ans=[]
t=N
while t != 0:
    if t%(-2)==0:
        ans.append('0')
        t //= -2
    else:
        ans.append('1')
        t=(t-1)//(-2)
        
ans = rereversed(ans)
print(''.join(ans))
        

### FIXED CODE ###

N = int(input())

L = [[0,1]]
i = 1
while True:
	d = (-2) ** i
	if d < 0:
		L.append([L[-1][0]+d,L[-1][1]])
	else:
		L.append([L[-1][0],L[-1][1]+d])

	a,b = L[-1]
	if a <= N <= b:
		break

	i += 1
		
ans = []
tmp = N
for i in reversed(range(len(L))):
	if i == 0:
		if tmp == 1:
			ans.append("1")
		else:
			ans.append("0")
		break

	add = (-2) ** i
	a,b = L[i]
	c,d = L[i-1]
	if a == c:
		if d < tmp <= b:
			ans.append("1")
			tmp -= add
			continue
	elif b == d:
		if a <= tmp < c:
			ans.append("1")
			tmp -= add
			continue

	ans.append("0")

if ans[0] == "0":
	ans.pop(0)

print("".join(ans))
s = input()
t = input()
n = len(s)
for i in range(n):
  if i%2:
    print(t[i], end="")
  else:
    print(s[i], end="")
print()

### FIXED CODE ###

s = input()
t = input()
n = len(t)
for i in range(n):
  print(s[i], end="")
  print(t[i], end="")
if len(s) != len(t):
  print(s[-1], end="")
print()
import numpy as np
import math
n = int(input())
x = []
y = []
for i in range(n):
  x_, y_ = list(map(int, input().split()))
  x.append(x_)
  y.append(y_)
val = 0
for i in range(n):
  for j in range(i+1, n):
    val += np.sqrt((x[i] - x[j])**2 + (y[i] - y[j])**2)

ans = val/math.factorial(n) * math.factorial(n-1) * 2
print(ans)

### FIXED CODE ###

N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
 
from itertools import permutations
from math import sqrt
 
paths = list(permutations(range(N), N))
l = len(paths)
total = 0
for path in paths:
    tmp = 0
    x, y = xy[path[0]][0], xy[path[0]][1]
    for p in path[1:]:
        px, py = xy[p][0], xy[p][1]
        tmp += sqrt((px-x)**2 + (py-y)**2)
    total += tmp
print(total / l)
S = input()
a = -1
z = len(S)
for i, c in enumerate(input()):
  if c == "A" and a == -1: a = i
  if c == "Z": z = i

print(z-a+1)

### FIXED CODE ###

a = -1
z = 0
for i, c in enumerate(input()):
  if c == "A" and a == -1: a = i
  if c == "Z": z = i

print(z-a+1)
n = int(input())
s = [input() for i in range(n)]
m = int(input())
t = [input() for i in range(m)]

print(max(s.count(S) - t.count(S) for S in s) + [0])

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
m = int(input())
t = [input() for i in range(m)]

print(max([s.count(S) - t.count(S) for S in s] + [0]))
a = []
while 1:
 s = input()
 if s == 'END_OF_TEXT':
  break
 else:
  s = list(s.split(''))
  s.remove('')
  s = list(s[0].split())
  a.append(s)

print(a.count(a[0]) - 1)

### FIXED CODE ###

word = input()
counter = 0
while 1:
 s = input()
 if s == 'END_OF_TEXT':
  break
 else:
  s = list(s.lower().split())
  counter += s.count(word)
  counter += s.count(word + '.')

print(counter)
from math import pi

r = float(input())
print(r * r * math.pi, 2 * r * math.pi)

### FIXED CODE ###

from math import pi

r = float(input())
print(r * r * pi, 2 * r * pi)
A = [0, 0, 0]
bool = 0
for i in range(3):
  A[i] = N % 10
  N = (N - A[i])/10
  if A[i] == 7:
    print('Yes')
    bool = 1
    break
if bool == 0:
    print('No')


### FIXED CODE ###

N = int(input())
A = [0, 0, 0]
bool = 0
for i in range(3):
  A[i] = N % 10
  N = (N - A[i])/10
  if A[i] == 7:
    print('Yes')
    bool = 1
    break
if bool == 0:
    print('No')
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re
import math
import collections
import itertools
import functools

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)

def solve_small(K):
    if K == 0:
        return [0, 1]
    elif K == 1:
        return [0, 2]

    return [i for i in range(1, K+1)]

def solve(K):
    N = 50
    q = K // N
    r = K %  N

    if q < 10000 || r < 10:
        A = [q+i-r for i in range(N)]
        A[-1] += r + r*N
    else:
        A = [q+i-3*r for i in range(N)]
        A[-3] += r + r*N - 2
        A[-2] += r + r*N - 1
        A[-1] += r + r*N - 0
        A[-1] -= 2*r

    return A

def main():
    K = int(input())

    if K < 50:
        A = solve_small(K)
    else:
        A = solve(K)

    print(len(A))
    print(" ".join(map(str, A)))

if __name__ == "__main__": main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re
import math
import collections
import itertools
import functools

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)

def solve_small(K):
    if K == 0:
        return [0, 1]
    elif K == 1:
        return [0, 2]

    return [i for i in range(1, K+1)]

def solve(K):
    N = 50
    q = K // N
    r = K %  N

    A = [q+i for i in range(N)]
    for i in range(r):
        for j in range(N):
            if j == i:
                A[j] += N
            else:
                A[j] -= 1

    return A

def main():
    K = int(input())

    if K < 50:
        A = solve_small(K)
    else:
        A = solve(K)

    print(len(A))
    print(" ".join(map(str, A)))

if __name__ == "__main__": main()
import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N, K = map(int, input().split())
mod = 1e+9 + 7

for i in range(1, K+1):
    print(int(combinations_count(N-K+1, i) * combinations_count(K-1, i-1) % mod))


### FIXED CODE ###

import math


def combinations_count(n, r):
    if n >= r:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    else:
        return 0


N, K = map(int, input().split())
mod = int(1e+9 + 7)
for i in range(1, K+1):
    print(int(combinations_count(N-K+1, i) * combinations_count(K-1, i-1) % mod))
import sys,collections,math,random,fractions,bisect;sys.setrecursionlimit(10**7)
sr = sys.stdin.readline; P = print; P2 = lambda x: print(*x, sep="\n")
def I(i=0): t = [int(x)-i for x in sr().split()];return t if len(t) > 1 else t[0]
def S(): t = sr().split(); return t if len(t) > 1 else t[0]
L1,L2,L3,L4, = [],[],[],[]
 
H,N = I()
A = I()
if sum([A]) >= H:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import sys,collections,math,random,fractions,bisect;sys.setrecursionlimit(10**7)
sr = sys.stdin.readline; P = print; P2 = lambda x: print(*x, sep="\n")
def I(i=0): t = [int(x)-i for x in sr().split()];return t
def S(): t = sr().split(); return t if len(t) > 1 else t[0]
L1,L2,L3,L4, = [],[],[],[]
 
H,N = I()
A = I()
if sum(A) >= H:
    print("Yes")
else:
    print("No")
n = int(input())
a = []
for i in range(n):
  a.apped(str(input()))
print(len(set(a)))

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(str(input()))
print(len(set(a)))
import sys
S = sys.argv
if S[2]==S[3] and S[4]==S[5]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

S = input()
if S[2]==S[3] and S[4]==S[5]:
  print('Yes')
else:
  print('No')
c=raw_input()
if c==a or c==e or c==i or c==o or c==u:
  print "vowel"
else:
  print "consonant"

### FIXED CODE ###

c=raw_input()
if c in "a,e,i,o,u":
  print "vowel"
else:
  print "consonant"
n,m=map(int,input().split())
edge=[n*[0]for _ in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	a-=1
	b-=1
	edge[a][b]=edge[b][a]=1
from itertools import permutations
ans=0
for i in permutations([j for j in range(1,n)],n-1):
	f=True
	t=[0]+i
	for j in range(1,n):
		if edge[t[j-1]][t[j]]==0:f=False
	if f:ans+=1
print(ans)

### FIXED CODE ###

z,m=map(int,input().split());a=[[],[]];ans=0
for i in range(m):aa,bb=map(int,input().split());a[0].append(aa);a[1].append(bb)
def d(n,nl,ml):
  if sorted(nl+[n])==[i+1for i in range(z)]:return 1
  if n in nl:return 0
  l=len(ml[0]);ans=0
  for i in range(l):
    c=[ml[0][:i]+ml[0][i+1:],ml[1][:i]+ml[1][i+1:]]
    if ml[0][i]==n:ans+=d(ml[1][i],nl+[n],c)
    if ml[1][i]==n:ans+=d(ml[0][i],nl+[n],c)
  return ans
for i in range(m):
  if a[0][i]==1:
    c=[a[0][:i]+a[0][i+1:],a[1][:i]+a[1][i+1:]]
    ans+=d(a[1][i],[1],c)
print(ans)
import statistics

def main():
    n = int(input())
    A = [int(e) for e in input().split()]

    B = [a - ai - 1 for ai, a in enumerate(A)]
    m = int(statistics.median(B))
    ans = sum([abs(b - m) for b in B])
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import statistics

def main():
    n = int(input())
    A = [int(e) for e in input().split()]

    B = [a - ai - 1 for ai, a in enumerate(A)]
    m = int(statistics.median(B))
    ans = sum([abs(b - m) for b in B])
    print(ans)

if __name__ == "__main__":
    main()
n=int(input())
x=input()
p=x.count('1')

#popcount(x)が0,1だった場合に対応
if p==0:
    exit()
    for i in range(n):
        print(1)
    exit()
#elif p==1:
#    z=x.index('1')
#    for i in range(n):
#        if i==z:
#            print(0)
#        else:
#            print(1)
#    exit()

#愚直に解く関数を定義
def solve(n):
    count=0
    while n:
        popcount=bin(n).count('1')
        n%=popcount
        count+=1
    return count

#2^i mod(p+1),2^i mod(p-1)のリストを作成
a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))

#x mod(p+1),x mod(p-1)を計算
a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]

#本計算
for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i])%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp)+1)

### FIXED CODE ###

n=int(input())
x=input()
p=x.count('1')

#愚直に解く関数を定義
def solve(n):
    count=0
    while n:
        popcount=bin(n).count('1')
        n%=popcount
        count+=1
    return count+1

#popcount(x)が0,1だった場合に対応
if p==0:
    for i in range(n):
        print(1)
    exit()
elif p==1:
    z=x.index('1')
    t=pow(2,n-z-1,p+1)
    for i in range(n):
        if i==z:
            print(0)
        else:
            tmp=(t+pow(2,n-i-1,p+1))%(p+1)
            print(solve(tmp))
    exit()


#2^i mod(p+1),2^i mod(p-1)のリストを作成
a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))

#x mod(p+1),x mod(p-1)を計算
a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]

#本計算
for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i])%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp))
import numpy as np
import copy

a = map(int,raw_input().split())
H = a[0]
W = a[1]
A = []
for idx in xrange(H):
  A.append( list(raw_input()) )

def textMap(A):
  A = np.array(A, dtype='S')
  A[A!='0'] = '#'
  A[A=='0'] = '.'
  texts = []
  for vec in A:
    texts.append( ''.join(vec) )
  return '\n'.join(texts)

def myfunc(H,W,A):
  A = np.array(A)
  A[A=='#'] = 1
  A[A=='.'] = 0
  A = np.array(A, dtype=np.int)
  T = np.zeros((H,W), dtype=np.int)
  O = np.zeros((H,W), dtype=np.int)
  T[:,0] = 1
  O[:,-1] = 1
  if H%2 == 0:
    for idx in xrange(H/2):
      T[idx*2,1:-1] = 1
      O[idx*2+1,1:-1] = 1
  else:
    for idx in xrange(H/2):
      T[idx*2,1:-1] = 1
      O[idx

### FIXED CODE ###

import numpy as np
import copy

a = map(int,raw_input().split())
H = a[0]
W = a[1]
A = []
for idx in xrange(H):
  A.append( list(raw_input()) )

def textMap(A):
  A = np.array(A, dtype='S')
  A[A!='0'] = '#'
  A[A=='0'] = '.'
  texts = []
  for vec in A:
    texts.append( ''.join(vec) )
  return '\n'.join(texts)

def myfunc(H,W,A):
  A = np.array(A)
  A[A=='#'] = 1
  A[A=='.'] = 0
  A = np.array(A, dtype=np.int)
  T = np.zeros((H,W), dtype=np.int)
  O = np.zeros((H,W), dtype=np.int)
  T[:,0] = 1
  O[:,-1] = 1
  if H%2 == 0:
    for idx in xrange(H/2):
      T[idx*2,1:-1] = 1
      O[idx*2+1,1:-1] = 1
  else:
    for idx in xrange(H/2):
      T[idx*2,1:-1] = 1
      O[idx*2+1,1:-1] = 1
    T[-1,1:-1] = 1
  T[A==1] += 1
  O[A==1] += 1

  tT = textMap(T)
  tO = textMap(O)
  print '\n'.join([tT,'',tO])

myfunc(H,W,A)
def check(m,g,A,n):
    
    for i in range(n):
        gg = g + A[n-i-1]
        if m == gg:
            return True
        elif n == 0 or m < gg:
            continue
        if check(m,gg,A,n-i-1) == True:
            return True
    return False
        

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

mini = min(A)
nor = sum(A)

for mi in m:
    if mi < mini or mi > nor:
        print(no)
    if check(mi,0,A,n):
        print("yes")
    else:
        print("no")

### FIXED CODE ###

def check(m,g,A,n):
    
    for i in range(n):
        gg = g + A[n-i-1]
        if m == gg:
            return True
        elif n == 0 or m < gg:
            continue
        if check(m,gg,A,n-i-1) == True:
            return True
    return False
        

    

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




mini = min(A)
nor = sum(A)

for mi in m:
    if mi < mini or mi > nor:
        print("no")
        continue
    if check(mi,0,A,n):
        print("yes")
    else:
        print("no")
def function(n):
    if n <= 1:
        return 1
    else:
        return function(n-1) + function(n-2)

N, M = (int(x) for x in input().split())
a = [-1]
for i in range(M):
    a.append(int(input()))

a.append(N+1)
ans = 1
for i in range(M+1):
    length = a[i+1] - a[i] - 1
    if length == 0:
        print(0)
        exit()
    else:
        ans *= function(length-1)

print(ans%(10**9+7))


### FIXED CODE ###

N, M = (int(x) for x in input().split())
F = [0,1]
for i in range(N):
    F.append(F[i]+F[i+1])

a = [-1]
for i in range(M):
    a.append(int(input()))

a.append(N+1)
ans = 1
for i in range(M+1):
    length = a[i+1] - a[i] - 1
    if length == 0:
        print(0)
        exit()
    else:
        ans *= F[length]

print(ans%(10**9+7))
import sys
t='X'
for e in sys.stdin:
 for i in'0123456789'[(e[0]==t)*('+'!=e[1])or('+X'in e)*('+X='not in e)or('=X'in e)*(e[-2]=='='):]:
  if eval(e.replace(t,i).replace('=','==')):print(i);break
 else:print('NA')


### FIXED CODE ###

import sys
p,t='+X'
for e in sys.stdin:
 for i in'0123456789'[(e[0]==t)*(e[1]!=p)or('+X'in e)*('+X='not in e):]:
  l,r=e.replace(t,i).split('=')
  if sum(map(int,l.split(p)))==int(r):print(i);break
 else:print('NA')
N, M = map(int, input().split())
features = list()
for _ in range(N):
    f = map(int, input().split())
    features.append(list(f))

maximum = 0
index = list(itertools.combinations(range(0, N), M))
for i in index:
    s1, s2, s3 = 0, 0, 0
    for j in i:
        s1 += features[j][0]
        s2 += features[j][1]
        s3 += features[j][2]
    s = abs(s1) + abs(s2) + abs(s3)
    if s > maximum:
        maximum = s
print(maximum)

### FIXED CODE ###

N, M = map(int, input().split())
ppp, ppm, pmp, pmm, mpp, mpm, mmp, mmm = list(), list(), list(), list(), list(), list(), list(), list()
for _ in range(N):
    x, y, z = map(int, input().split())
    ppp.append(x + y + z)
    ppm.append(x + y - z)
    pmp.append(x - y + z)
    pmm.append(x - y - z)
    mpp.append(- x + y + z)
    mpm.append(- x + y - z)
    mmp.append(- x - y + z)
    mmm.append(- x - y - z)
tmp = [sum(sorted(ppp, reverse=True)[:M]), sum(sorted(ppm, reverse=True)[:M]), sum(sorted(pmp, reverse=True)[:M]), sum(sorted(pmm, reverse=True)[:M]),
       sum(sorted(mpp, reverse=True)[:M]), sum(sorted(mpm, reverse=True)[:M]), sum(sorted(mmp, reverse=True)[:M]), sum(sorted(mmm, reverse=True)[:M])]
out = max(tmp)
print(out)
from collections import deque   
n = int(input())
d = deque()
for _ in range(n):
    x = input().split()
    if (command[0][0] == 'i'):
        d.appendleft(int(x[1]))
    elif (command[0] == 'delete'):
        try:
            d.remove(int(x[1]))
        except ValueError:
            pass
    elif (x[0][6] == 'F'):
        d.popleft()
    else:
        d.pop()
print(*xdeque)



### FIXED CODE ###

from collections import deque
n = int(input())
a = deque()
for i in range(n):
    c = input()
    if c == "deleteFirst":
        a.popleft()
    elif c == "deleteLast":
        a.pop()
    else:
        c, v = c.split()
        if c == "insert":
            a.appendleft(v)
        else:
            try:
                a.remove(v)
            except:
                pass
print(" ".join(a))
a.b=map(int,input().split())
print((a+b)%24)

### FIXED CODE ###

a,b=map(int,input().split())
print((a+b)%24)
n=int(input)
ans = 1
while ans**2 <= n:
  ans += 1
ans -= 1
print(ans**2)

### FIXED CODE ###

n=int(input())
ans = 1
while ans**2 <= n:
  ans += 1
ans -= 1
print(ans**2)
import itertools
S,M,L = 5,9,13
ref = {5:1,9:2,13:3}
dx = [0, 0, 1, 0,-1, 1, 1,-1,-1, 2, 0,-2, 0]
dy = [0,-1, 0, 1, 0,-1, 1, 1,-1, 0, 2, 0,-2]

def minus(C,x,y,size):
	for i in range(size):
		try: C[y+dy[i]][x+dx[i]] -= 1
		except: pass

def canMinus(C,x,y,size):
	for i in range(size):
		try:
			if C[y+dy[i]][x+dx[i]] == 0:
				return False
		except: pass
	return True

def canMinusList(C,size):
	ls = []
	for y in range(10):
		for x in range(10):
			if canMinus(C,x,y,size):
				ls.append([x,y])
	return ls

def copy(C):
	C_copy = [C[i][:] for i in range(len(C))]
	return C_copy

def tryFindAns(Cloth,drop,p,Rslt):
	size,num = drop[p][0],drop[p][1]
	canList = canMinusList(Cloth,size)
	for comb in itertools.combinations(canList,num):
		rslt = copy(Rslt)
		C = copy(Cloth)
		for x,y in comb:
			if  canMinus(C,x,y,size):
				minus(C,x,y,size)
				rslt.append([x,y,size])
			else:
				break
		else:
			if p+1 == len(drop):
				return rslt
			else:
				return tryFindAns(C,drop,p+1,rslt)

def findAns(Cloth,drop):
	for i in range(2,-1,-1):
		if drop[i][1] == 0:
			drop.pop(i)
	p,rslt = 0,[]
	return tryFindAns(Cloth,drop,p,rslt)

n = int(raw_input())
Cloth = [map(int, raw_input().split()) for i in range(10)]
sm = sum([sum(Cloth[i]) for i in range(10)])
dropList = []

for s in range(n):
	m4 = 13*n-sm-8*s
	if m4 < 0: break
	if m4%4 == 0:
		m = m4/4
		if s+m <= n:
			dropList.append([[13,n-s-m],[9,m],[5,s]])

for drop in dropList:
	ans = findAns(Cloth,drop)
	if ans is not None:
		break

for a in ans:
	print  a[0],a[1],ref[a[2]]

### FIXED CODE ###

import itertools
ref = {5:1,9:2,13:3}
dx = [0, 0, 1, 0,-1, 1, 1,-1,-1, 2, 0,-2, 0]
dy = [0,-1, 0, 1, 0,-1, 1, 1,-1, 0, 2, 0,-2]

def isOn(x,y):
    return 0<=x<10 and 0<=y<10

def minus(C,x,y,size):
    for i in range(size):
        C[y+dy[i]][x+dx[i]] -= 1

def plus(C,x,y,size):
    for i in range(size):
        C[y+dy[i]][x+dx[i]] += 1

def canMinus(C,x,y,size):
    return all([isOn(x+dx[i],y+dy[i]) and C[y+dy[i]][x+dx[i]]>0 for i in range(size)])

def findAns(C,drops,sp):
    if len(drops) == 0:
        return []
    for i in range(sp,100):
        if C[i/10][i%10] > 0:
            break
        sp += 1
    for size in set(drops):
        for i in range(size):
            sx,sy = sp%10+dx[i],sp/10+dy[i]
            if isOn(sx,sy) and C[sy][sx] > 0:
                if canMinus(C,sx,sy,size):
                    minus(C,sx,sy,size)
                    drops.remove(size)
                    ans = findAns(C,drops,sp)
                    if ans != False:
                        ans.append([sx,sy,size])
                        return ans
                    drops.append(size)
                    plus(C,sx,sy,size)
    return False

n = int(raw_input())
C = [map(int, raw_input().split()) for i in range(10)]
sm = sum([sum(C[i]) for i in range(10)])
dropList = [list(a) for a in itertools.combinations_with_replacement([0,13,9,5],n) if sum(a) == sm]
for drops in dropList:
    ans = findAns(C,drops,0)
    if ans != False:
        break
        
for a in ans:
    print  a[0],a[1],ref[a[2]]
N, K = map(int, input().split(" "))

h = [int(input()) for i in range(N)]

sort_h = sorted(h)
diff_h = 0
ans = []
for i in range(K):
    diff_h = sort_h[i+(K-1)] - sort_h[i] 
    ans.append(diff_h)

print(min(ans))

### FIXED CODE ###


N, K = map(int, input().split(" "))

h = [int(input()) for i in range(N)]

sort_h = sorted(h)
diff_h = 0
ans = []
for i in range(len(h)-K+1):
    diff_h = sort_h[i+(K-1)] - sort_h[i] 
    ans.append(diff_h)

print(min(ans))
def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    _,s = sieve((10**6)+7)

    zero =  A.count(1)
    if zero>1:
        print(0)
        return
    if zero==1:
        print(1)
        return

    for i in range(lenb):
        for j in range(i+1,lenb):
            if Boo[j] and s[B[j]] and B[j] % B[i] == 0:
                Boo[j] = False

    cnt = 0
    for i in range(lenb):
        if Boo[i] and A.count(B[i])==1:
            cnt += 1

    print(cnt)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    ZENBU = [False]*(10**6+4)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    for i in range(lenb):
        temp = 2
        if ZENBU[B[i]]==False:
            while B[i]*temp < 1000002:
                ZENBU[B[i]*temp] = True
                temp+=1

    cnt = 0
    for i in range(lenb):
        if ZENBU[B[i]]==False and C[B[i]]==1:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()
for i in range(1,h+1):
    for j in range(0,w+2):
        if grid[i][j] == '#':
            if j >= 1:
                for k in range(j-start):
                    ans[i][starimport numpy as np
h,w = map(int,input().split())
ans = [[0]*(w+2) for _ in range(h+2)]
grid = []
grid.append(['#']*(w+2))
for _ in range(h):
    s = list(input())
    grid.append(['#'] + s + ['#'])
grid.append(['#']*(w+2))
print(grid)
for i in range(1,h+1):
    for j in range(0,w+2):
        if grid[i][j] == '#':
            if j >= 1:
                for k in range(j-start):
                    ans[i][start+k] += j-start
            start = j + 1
for j in range(1,w+1):
    for i in range(0,h+2):
        if grid[i][j] == '#':
            if i >= 1:
                for k in range(i-start):
                    ans[start+k][j] += i-start
            start = i + 1
print(np.amax(ans)-1)t+k] += j-start
            start = j + 1

### FIXED CODE ###

h,w = map(int,input().split())
ans = [[0]*(w+2) for _ in range(h+2)]
grid = []
grid.append(['#']*(w+2))
for _ in range(h):
    s = list(input())
    grid.append(['#'] + s + ['#'])
grid.append(['#']*(w+2))
for i in range(1,h+1):
    for j in range(0,w+2):
        if grid[i][j] == '#':
            if j >= 1:
                for k in range(j-start):
                    ans[i][start+k] += j-start
            start = j + 1
for j in range(1,w+1):
    for i in range(0,h+2):
        if grid[i][j] == '#':
            if i >= 1:
                for k in range(i-start):
                    ans[start+k][j] += i-start
            start = i + 1
print(max(list(map(lambda x:max(x),ans)))-1)
n, k = map(int, input().split())
snuke = [1 for i in range(n)]
for _ in range(k):
	d = int(input())
	a = list(map(int, input().split()))
	for i in range(a):
		snuke[i -1] = 0
		
print(sum(snuke))

### FIXED CODE ###

n, k = map(int, input().split())
snuke = [1 for i in range(n)]
for _ in range(k):
	d = int(input())
	a = list(map(int, input().split()))
	for i in a:
		snuke[i -1] = 0
		
print(sum(snuke))
n, k = map(int, input().split())
h = []

for i in range(n):
    h.append(int(input()))
min = 10 ** 10
#  print(h)
h = sorted(h)
#  print(h)
for i in range(k):
    #  print(h[i:i+k-1])
    div = h[i+k-1] - h[i]
    if div < min:
        min = div
    if min == 0:
        print(min)
        exit()
print(min)


### FIXED CODE ###

n, k = map(int, input().split())
h = []

for i in range(n):
    h.append(int(input()))
min = 10 ** 10
#  print(h)
h = sorted(h)
#  print(h)
for i in range(n-k+1):
    #  print(h[i:i+k-1])
    div = h[i+k-1] - h[i]
    if div < min:
        min = div
    if min == 0:
        print(min)
        exit()
print(min)