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

from collections import*
from copy import*
import sys
sys.setrecursionlimit(10**8)

n=int(input())
if n<90000:
    d=defaultdict(list)
    
    q=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        d[a].append(b)
        d[b].append(a)
        q.append(tuple(sorted([a,b])))
        
    #print(d)
    m=max(map(len,d.values()))
    print(m)
    
    dcolars={}
    
    def BFS(d,point,c):
        colar=deque(range(1,m+1))
        for i in d[point]:
            if tuple(sorted([point,i])) not in dcolars:
                ckamo=colar.pop()
                if c==ckamo:
                    csave=deepcopy(ckamo)
                    ckamo=colar.pop()
                    colar.append(csave)
                dcolars[tuple(sorted([point,i]))]=ckamo
                BFS(d,i,ckamo)
        return dcolars
    
    ans=BFS(d,1,0)
    
    for i in q:
        print(ans[i])

else:
    d=defaultdict(list)
    
    q=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        d[a].append(b)
        d[b].append(a)
        q.append(tuple(sorted([a,b])))
        
    #print(d)
    m=max(map(len,d.values()))
    print(m)
    
    dcolars={}
    
    def BFS(d,point,c):
        colar=0
        for i in d[point]:
            colar+=1
            if tuple(sorted([point,i])) not in dcolars:
                if c==colar:
                    colar+=1
                dcolars[tuple(sorted([point,i]))]=colar
                dcolars[tuple(sorted([point,i])[::-1])]=colar
                BFS(d,i,colar)
    
        return dcolars
    
    ans=BFS(d,1,0)
    
    for i in q:
        print(ans[i])

### FIXED CODE ###

from collections import*
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline

n=int(input())
d={}

q=[]
for i in range(n-1):
    a,b=map(int,input().split())
    if a not in d:
        d[a]=[]
    if b not in d:
        d[b]=[]
    d[b].append(a)
    d[a].append(b)        
    q.append(tuple(sorted([a,b])))

m=max(map(len,d.values()))
print(m)

dcolars={}

def BFS(d,point,c):
    for i in d[point]:
        if tuple(sorted([point,i])) not in dcolars:
            c+=1
            if c==m+1:
                c=1
            dcolars[tuple(sorted([point,i]))]=c
            BFS(d,i,c)
    return dcolars

ans=BFS(d,1,0)

for i in q:
    print(ans[i])
### BUGGY CODE ###

S = input()
MOD = 10**9 + 7
lenS = len(S)

dp = [[0 for _ in range(13)] for _ in range(lenS + 1)]  # dp[digit][d] = digit桁までの mod=d の数
dp[0][0] = 1

digitMask = 1

for digit in range(1, lenS + 1) :
    if(S[-digit] == '?') :
        for d in range(13) :
            for k in range(10) :
                dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - k * digitMask) % 13]) % MOD
    else :
        a = int(S[-digit])
        for d in range(13) :
            dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - a * digitMask) % 13]) % MOD
    digitMask *= 10

ans = (dp[len(S)][5]) % MOD
print(ans)



### FIXED CODE ###

S = input()
MOD = 10**9 + 7
lenS = len(S)

dp = [[0 for _ in range(13)] for _ in range(lenS + 1)]  # dp[digit][d] = digit桁までの mod=d の数
dp[0][0] = 1

digitMask = 1

for digit in range(1, lenS + 1) :
    if(S[-digit] == '?') :
        for d in range(13) :
            for k in range(10) :
                dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - k * digitMask) % 13]) % MOD
    else :
        a = int(S[-digit])
        for d in range(13) :
            dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - a * digitMask) % 13]) % MOD
    digitMask *= 10
    digitMask %= 13

ans = (dp[len(S)][5]) % MOD
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
As = list(map(int, input().split()))
 
 
def change(arr):
  newAs = [0] * n
  for i, a in enumerate(arr):
    for t in range(max(i - a, 0), min(i + a + 1, n)):
      newAs[t] += 1
  return newAs
 
 
for temp in range(min(k, 40)):
  As = change(As)
print(' '.join(map(str, As)))


### FIXED CODE ###

import math
from itertools import accumulate
n, k = map(int, input().split())
As = list(map(int, input().split()))
for i in range(min(41, k)):
  _As = [0]*(n+1)
  for j in range(n):
    l = max(0, j - As[j])
    r = min(n - 1, j + As[j])
    _As[l] += 1
    _As[r+1] -= 1
  As = list(accumulate(_As))[:-1]
print(' '.join([str(A) for A in As]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int,input().split())

neighbor = {}
for i in range(1,n+1):
    neighbor[i] = []

for i in range(n-1):
    x, y = map(int,input().split())
    neighbor[x].append(y)
    neighbor[y].append(x)

dp = [{} for _ in range(n+1)]
for i in range(1,n+1):
    for j in neighbor[i]:
        dp[i][j] = -1

def calc_dp(x, y):
    if(dp[x][y] != -1):
        return(dp[x][y])

    if(len(neighbor[y]) == 1):
        dp[x][y] = 2 % m
        return(dp[x][y])

    temp = 1
    for i in neighbor[y]:
        if(i == x):
            continue

        temp = temp * (calc_dp(y,i)) % m

    temp = (temp + 1) % m
    dp[x][y] = temp
    return(temp)

for i in range(1,n+1):
    ans = 1
    for j in neighbor[i]:
        ans = ans * calc_dp(i,j) % m
    print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
mod = m
# mod = 10**9+7

# 前準備
import sys
input = sys.stdin.readline
from collections import deque

graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

ini = 1

def calc(a,b):
    p = a * b % mod
    return p

# calc1 の定義
def calc1(c,p):
    p_num = ini
    for i in graph[c]:
        if i == p:
            continue
        p_num = calc(p_num, dp1[i])
    p_num += 1
    dp1[c] = p_num % mod

# calc2 の定義
def calc2(p):
    arr = [dp1[c] if c != parent[p] else dp2[p] for c in graph[p]]

    left = [ini]
    for i in arr[:-1]:
        left.append( calc(left[-1], i ) )
    right = [ini]
    for i in arr[:0:-1]:
        right.append( calc(right[-1], i) )
    right = right[::-1]

    prod = []
    for a,b in zip(left,right):
        prod.append(calc(a,b))

    for c,x in zip(graph[p], prod):
        if(c != parent[p]):
            dp2[c] = (x + 1)%mod



# 根から探索して親と探索順を記録
root = 1
order = []
parent = [0] * (n+1)
stack = deque()
stack.append(root)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        stack.append(y)
        parent[y] = x

# 親→子の値を算出
dp1 = [None] * (n+1)
for i in order[::-1]:
    calc1(i, parent[i])

# 子→親の値を算出　累積和チックにすることでうに対策。
dp2 = [None] * (n+1)
dp2[root] = ini
for i in order:
    calc2(i)

for i in range(1,n+1):
    ans = calc(dp1[i]-1, dp2[i])
    print(ans)
### BUGGY CODE ###

import sys
from scipy.sparse.csgraph import dijkstra
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
INF = float('inf')
graph = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    graph[i][i] = 0

for _ in range(N - 1):
    a, b, c = map(int, readline().split())
    graph[a][b] = c
    graph[b][a] = c

Q, K = map(int, readline().split())
distance = dijkstra(graph, indices=K)

xy = map(int, read().split())
for x, y in zip(xy, xy):
    print(int(distance[x] + distance[y]))

### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 6)


def main():
    N = int(readline())
    edge = [[] for _ in range(N + 1)]

    for _ in range(N - 1):
        a, b, c = map(int, readline().split())
        edge[a].append((b, c))
        edge[b].append((a, c))

    Q, K = map(int, readline().split())

    distance = [None] * (N + 1)


    def measure_distance(v, d):
        distance[v] = d
        for vv, dd in edge[v]:
            if distance[vv] is not None:
                continue
            measure_distance(vv, d + dd)


    measure_distance(K, 0)

    xy = map(int, read().split())
    for x, y in zip(xy, xy):
        print(distance[x] + distance[y])


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

import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import queue
INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.judge = "Yes"
		self.prev = [None] * N
		self.path = []
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.Q.put(i)
					self.visit[i] = "Yes"
					self.prev[i] = v
				else:
					if i == s:
						self.judge = "No"
						#閉路path構築
						while True:
							self.path.append(v)
							v = self.prev[v]
							if v == None:
								break
		
			if self.judge == "No":
				break
		# print(self.path)

	def cycle(self):
		if self.judge == "No":
			return len(self.path), list(reversed(self.path))
		else:
			return INF, []

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, M = getlist()
	G = Graph()
	for i in range(M):
		A, B = getlist()
		A -= 1; B -= 1
		G.add_edge(A, B)

	cycle_dist = INF
	cycle_path = None
	for i in range(N):
		BF = BFS(G, i, N)
		dist_var, dist_path = BF.cycle()
		if dist_var < cycle_dist:
			cycle_dist = dist_var
			cycle_path = dist_path

	if cycle_dist == INF:
		print(-1)
	else:
		print(cycle_dist)
		for i in cycle_path:
			print(i + 1)


if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def BFS(G, N, s, g, ans):
	Q = deque()
	Q.append(s)
	dist = [INF] * N
	dist[s] = 0
	prev = [None] * N
	jud = "No"
	while Q:
		v = Q.popleft()
		for i in G.graph[v]:
			if dist[i] == INF:
				dist[i] = dist[v] + 1
				prev[i] = v
				Q.append(i)
				if i == g:
					jud = "Yes"
					break
		if jud == "Yes":
			break

	if ans > dist[g]:
		state = g
		path = [g]
		while True:
			state = prev[state]
			path.append(state)
			if state == s:
				break
		return dist[g], path[::-1]
	else:
		return INF, []

#処理内容
def main():
	N, M = getlist()
	G = Graph()
	edgefrom = []
	edgeto = []
	for i in range(M):
		a, b = getlist()
		a -= 1; b -= 1
		edgefrom.append(a)
		edgeto.append(b)
		G.add_edge(a, b)

	ans = 100000
	path = None
	for i in range(M):
		predis, prepath = BFS(G, N, edgeto[i], edgefrom[i], ans)
		if predis != INF:
			ans = predis
			path = prepath

	if ans == 100000:
		print(-1)
	else:
		print(ans + 1)
		for i in path:
			print(i + 1)

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

n=int(input())

s=[]
for i in range(n):
    s.append(sorted(input()))

count=0
for i in range(n-1):
    for j in range(n-i-1):
        if s[i]==s[n-j-1]: 
            count=count+1

print(count)

### FIXED CODE ###

n =int(input())

s=[]
ans=0
count=1

for i in range(n):
    s.append("".join(sorted(input())))

s.sort()
for i in range(n-1):
    if s[i] == s[i+1]:
        count=count+1
    else:
        ans=ans+count*(count-1)/2
        count=1

ans=ans+count*(count-1)/2

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

n  = int(input())
m  = 10 ** 9 + 7
xs = [int(x) for x in input().split()]
bs = [0] * 61
b  = 1

for x in xs:
	e = 0
	
	while 0 < x:
		if x % 2 == 1:
			bs[e] += 1
			
		e  += 1
		x //= 2

b = 1
r = 0

for i in range(0, 61):
	if 0 < bs[i] and bs[i] < n:
		r += ((n - bs[i]) * bs[i]) * b
		
	b <<= 1
	
print(r % m)


### FIXED CODE ###

n  = int(input())
m  = 10 ** 9 + 7
xs = [int(x) for x in input().split()]
bs = [0] * 60
b  = 1

for x in xs:
	e = 0
	
	while 0 < x:
		if x % 2 == 1:
			bs[e] += 1
			
		e  += 1
		x //= 2

b = 1
r = 0

for i in range(0, 60):
	r  += ((n - bs[i]) * bs[i]) * b
	b <<= 1
	
print(r % m)
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
t=0
#移動回数
c=0
for i in range(n-1):
    c=0
    for j in range(n-i-1):
        if h[i+j]>=h[i+j+1]:
            c+=1
        else:
            break
    if c>=t:
        t=c
print(t)

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
count=0
t=0
for i in range(n-1):
    if h[i]>=h[i+1]:
        t+=1
    else:
        count=max(count,t)
        t=0
    count=max(count,t)
print(count)
### BUGGY CODE ###

#5.3
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

findCount = 0

for t in T:
    left = 0
    right = n
    center = right // 2
    preCenter= 0
    while left < right:
        if S[center] == t:
            findCount += 1
            break
        
        if S[center] >= t:
            right = center
        else:
            left = center
        
        center = (left + right) // 2

print(findCount)

### FIXED CODE ###

#5.3
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

findCount = 0

for t in T:
    left = 0
    right = n
    center = right // 2
    preCenter= 0
    while left < right:
        if S[center] == t:
            findCount += 1
            break
        
        if S[center] > t:
            right = center
        else:
            left = center + 1
        
        center = (left + right) // 2

print(findCount)
### BUGGY CODE ###

import numpy as np

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

B = np.array([0] * N)

for idx in range(N, 0, -1):
    a = A[idx - 1]

    q = N // idx

    target = [idx * i - 1 for i in range(2, q + 1)]
    r = sum(B[target]) % 2

    if a == 0:
        if r == 1:
            B[idx - 1] = 1
        else:
            B[idx - 1] = 0
    else:
        if r == 1:
            B[idx - 1] = 0
        else:
            B[idx - 1] = 1

g = sum(B)
print(g)

if g != 0:
    print(*list(np.where(B == 1)[0] + 1))

### FIXED CODE ###

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

B = [0] * N

out = []
for idx in range(N, 0, -1):
    a = A[idx - 1]

    q = N // idx

    cnt = 0
    for j in range(2, q + 1):
        if B[idx * j - 1] == 1:
            cnt += 1

    r = cnt % 2

    if a == 0:
        if r == 1:
            B[idx - 1] = 1
            out.append(idx)
        else:
            B[idx - 1] = 0
    else:
        if r == 1:
            B[idx - 1] = 0
        else:
            B[idx - 1] = 1
            out.append(idx)

g = sum(B)
print(g)

if g != 0:
    print(*out)
### BUGGY CODE ###

N, M = map(int,input().split())
L1 = [set() for k in range(N+1)]
for k in range(M):
	u, v = map(int, input().split())
	L1[u].add(v)
S, T = map(int, input().split())
L2 = [None for k in range(N+1)]
L3 = [None for k in range(N+1)]
for n in range(N+1):
	a = set()
	for l in L1[n]:
		a = a.union(L1[l])
	L2[n] = a
	a = set()
	for l in L2[n]:
		a = a.union(L1[l])
	a.discard(n)
	L3[n] = a
t = 0
sumi = set([S])
now = set([S])
flg = 0
ansT = set([T])
while(len(now) != 0):
	t +=1
	pre = set()
	for d in now:
		pre = pre.union(L3[d])
	now = pre - sumi
	sumi = sumi.union(now)
	if ansT <= sumi:
		print(t)
		flg = 1
		now = set()
if flg == 0:
	print(-1)

### FIXED CODE ###

N, M = map(int,input().split())
L1 = [[] for k in range(3*(N+1))]
for k in range(M):
	u, v = map(int, input().split())
	L1[3*u].append(3*v+1)
	L1[3*u+1].append(3*v+2)
	L1[3*u+2].append(3*v)
S, T = map(int, input().split())
S = 3*S
T = 3*T

t = 0
sumi = [None for k in range(3*(N+1))]
sumi[T] = -1
now = [S]
flg = 0
while(len(now) != 0):
	t += 1
	pre = []
	for n in now:
		pre.extend(L1[n])
	now = []
	for p in pre:
		if sumi[p] == None:
			sumi[p] = t
			now.append(p)
		elif sumi[p] == -1:
			flg = 1
	if flg == 1:
		print(t//3)
		flg = 2
		break
if flg == 0:
	print(-1)
### BUGGY CODE ###

import sys

import numpy as np

readline = sys.stdin.buffer.readline


def f(N, K, A):
    p = 0
    for i in range(K):
        C = np.zeros(N, dtype=np.int64)
        for j, a in enumerate(A):
            C[max(0, j - a):min(j + a + 1, N)] += 1
        A = C

        if len(set(A)) == 1:
            p += 1
            if p == 2:
                break
    return A


def solver():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    A = f(N, K, A)
    print(*A)


solver()


### FIXED CODE ###

import sys

from numba import njit

import numpy as np

readline = sys.stdin.buffer.readline


@njit('i8[:](i8, i8, i8[:])', cache=True)
def f(N, K, A):
    for i in range(min(K, 100)):
        C = np.zeros(N + 1, dtype=np.int64)

        for j, a in enumerate(A):
            l = max(0, j - a)
            r = min(j + a + 1, N)
            C[l] += 1
            C[r] -= 1

        A = np.cumsum(C)

    return A


def solver():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    A = f(N, K, np.array(A))
    print(*A[:-1])


solver()
### BUGGY CODE ###

n,k = map(int, input().split())
d={}
l = list(map(int, input().split()))
for i in range(len(l)):
    d[i+1] = l[i]

city = 1
l2 = [1]
while True:
    city = d[city]
    if city in l2:
        break
    l2.append(city)
first = l2.index(city)
if len(l2) <= k:
    if city == l2[-1]:
        print(city)
    else:
        l2 = l2[first:]
        print(l2[(k-first)%(len(l2))])
else:
    print(l2[k])

### FIXED CODE ###

n,k = map(int, input().split())
l = [0]+list(map(int, input().split()))

journey = [1]

for i in range(2*n):
    next = l[journey[-1]]
    journey.append(next)
if k <= n+1:
    print(journey[k])
    exit()

end = n
start = n-1

while journey[start] != journey[end]:
    start -= 1

period = end - start
k %= period

while k < n:
    k += period

print(journey[k])
### BUGGY CODE ###

import sys
import collections

n = int(input())
a = sys.stdin.readline().split()
c = collections.Counter(a)
for i in a:
    ans = 0
    for j in c.keys():
        if i == j:
            ans += (c[j]-1)*(c[j]-2)//2
        else:
            ans += c[j]*(c[j]-1)//2
    print(ans)


### FIXED CODE ###

import sys
import collections

n = int(input())
a = list(map(int, sys.stdin.readline().split()))
c = collections.Counter(a)
ans = [0 for i in range(sorted(c.keys())[-1]+1)]

for i in c.keys():
    ans[i] = c[i]*(c[i]-1)//2

sans = sum(ans)
for i in a:
    print(sans - ans[i] + ans[i]*(c[i]-2)//c[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[0]*N,[0]*N
dx,dy={},{}
for i in range(N):
    X[i],Y[i]=map(int,input().split())
    if X[i] in dx:
        dx[X[i]].append(i)
    else:
        dx[X[i]]=[i]
    if Y[i] in dy:
        dy[Y[i]].append(i)
    else:
        dy[Y[i]]=[i]
ux,uy=list(set(X)),list(set(Y))
ux.sort()
uy.sort()
uxi={x:i for i,x in enumerate(ux)}
uyi={y:i for i,y in enumerate(uy)}
edge=[[] for i in range(N)]
for i,(x,y) in enumerate(zip(X,Y)):
    for index in dx[x]+dy[y]:
        edge[i].append((0,index))
    if uxi[x]>=1:
        nx=ux[uxi[x]-1]
        for index in dx[nx]:
            if index!=i:
                edge[i].append((abs(nx-x),index))
                edge[index].append((abs(nx-x),i))
    if uyi[y]>=1:
        ny=uy[uyi[y]-1]
        for index in dy[ny]:
            if index!=i:
                edge[i].append((abs(ny-y),index))
                edge[index].append((abs(ny-y),i))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[],[]
for i in range(N):
    x,y=map(int,input().split())
    X.append((y,i))
    Y.append((x,i))
X.sort(key=lambda t:t[0])
Y.sort(key=lambda t:t[0])
edge=[[] for i in range(N)]
for i in range(N-1):
    edge[X[i][1]].append((abs(X[i][0]-X[i+1][0]),X[i+1][1]))
    edge[X[i+1][1]].append((abs(X[i][0]-X[i+1][0]),X[i][1]))
    edge[Y[i][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i+1][1]))
    edge[Y[i+1][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i][1]))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))
def gcd(L):
    while True:
        NL = []
        #print(L)
        minb = L[0]
        for l in L:
            r = l % minb
            if r != 0:
                NL.append(r)
        if(len(NL) == 0):
            return minb
        NL.append(minb)
        L = NL

lgcd = [0] * N
rgcd = [0] * N

for i in range(N):
    lgcd[i] = gcd(A[0:i+1])
    rgcd[i] = gcd(A[i:])
maxg = max(lgcd[N-2],rgcd[1])
for i in range(1,N-1):
    g = gcd([lgcd[i-1],rgcd[i+1]])
    if maxg < g:
        maxg = g

print(maxg)


### FIXED CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))
def gcdaaaaaaaaa(L):
    nextminb = L[0]
    nextn = len(L)
    while True:
        n = nextn
        minb = nextminb
        for l in L[:n]:
            nextn = 0
            r= l % minb
            
            if r != 0:
                L[nextn] = r
                nextn += 1
                if r < nextminb :
                    nextminb = r
        if minb == nextminb:
            return minb
        
def gcd(a,b):
    r = a % b
    if r == 0:
        return b
    else:
        return gcd(b,r)
def gcdL(L):
    g = L[0]
    for l in L:
        g = gcd(g,l)
    return g



lgcd = [0] * N
rgcd = [0] * N

lg = A[0]
rg = A[-1]
for i in range(N):
    
    lg = gcd(lg,A[i])
    lgcd[i] = lg
    rg = gcd(rg,A[N-i-1])
    rgcd[N-i-1] = rg
    
maxg = max(lgcd[N-2],rgcd[1])
for i in range(1,N-1):
    g = gcd(lgcd[i-1],rgcd[i+1])
    if maxg < g:
        maxg = g

print(maxg)
### BUGGY CODE ###

import pdb

def judgePrime(n):
  result = True
  for i in xrange(2, int(round(n))):
    if n % i == 0:
      result = False
      break
  return result

def getPrimeNumFromList(list):
  count = 0
  for i in xrange(len(list)):
    target = 0
    if i == 0:
      target = list[0]
      if judgePrime(target):
        count += 1
      else:
        pass

  return count

n = int(raw_input())
list = []

for i in xrange(n):
  list.append(int(raw_input()))
list.sort()

prime_list = []

while True:
  v = list.pop(0)
  if not judgePrime(v):
    continue
  prime_list.append(v)
  # print "list : "
  # print list
  # print "prime_list : "
  # print prime_list
  i = 0
  while True:
    # print "i = " + str(i)
    if i >= len(list):
      break
    elif list[i] % v == 0:
      list.pop(i)
      # print "i = " + str(i) + ", list: "
      # print list
    else:
      i += 1
  if len(list) == 0:
    break
  elif prime_list[len(prime_list) - 1] ^ 2 >= list[len(list) - 1]:
    prime_list.append(list)
    break

print len(prime_list)

### FIXED CODE ###

import pdb

n = int(raw_input())
count = 0
for x in xrange(n):
  target = int(raw_input())
  # pdb.set_trace()
  if target == 2:
    count += 1
  elif target < 3 or not target & 1:
    continue
  else:
    if pow(2, target - 1, target) == 1:
      count += 1

print count