You're given an integer $n$. For every integer $i$ from $2$ to $n$, assign a positive integer $a_i$ such that the following conditions hold:  For any pair of integers $(i,j)$, if $i$ and $j$ are coprime, $a_i \neq a_j$.  The maximal value of all $a_i$ should be minimized (that is, as small as possible). 

A pair of integers is called coprime if their greatest common divisor is $1$.


-----Input-----

The only line contains the integer $n$ ($2 \le n \le 10^5$).


-----Output-----

Print $n-1$ integers, $a_2$, $a_3$, $\ldots$, $a_n$ ($1 \leq a_i \leq n$). 

If there are multiple solutions, print any of them.


-----Examples-----
Input
4

Output
1 2 1 
Input
3

Output
2 1


-----Note-----

In the first example, notice that $3$ and $4$ are coprime, so $a_3 \neq a_4$. Also, notice that $a=[1,2,3]$ satisfies the first condition, but it's not a correct answer because its maximal value is $3$.

Source: codeforces | Difficulty: EASY
Tags: Number theory

Constructive algorithms


Solutions:
import math
n = int(input())
arr = [1, 2] + [0] * (n - 2)

def isprime(x):
	y = int(math.sqrt(x)) + 1
	for i in range(2, y):
		if x % i == 0:
			return i
	return x
p = 3
for i in range(4, n + 1):
	x = isprime(i)
	if x == i:
		arr[i - 2] = p
		p += 1
	else:
		arr[i - 2] = arr[x - 2]
print(*arr[:n - 1])


from sys import stdin, stdout
from itertools import combinations
from collections import defaultdict, OrderedDict
import math
import heapq

def listIn():
	return list(map(int, stdin.readline().strip().split()))

def stringListIn():
	return [x for x in stdin.readline().split()]

def intIn():
	return int(stdin.readline())

def stringIn():
	return stdin.readline().strip()

def primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def leastPrimeFactor(n):
	least_prime = [0] * (n + 1)
	least_prime[1] = 1
	for i in range(2, n + 1):
		if least_prime[i] == 0:
			least_prime[i] = i
			for j in range(2 * i, n + 1, i):
				if least_prime[j] == 0:
					least_prime[j] = i
	return least_prime
n = intIn()
A = leastPrimeFactor(n)
prime_n = sorted(set(A[2:]))
di = {}
c = 1
for ele in prime_n:
	di[ele] = c
	c += 1
ans = [0] * (n + 1)
for i in range(2, n + 1):
	ans[i] = di[A[i]]
print(*ans[2:])


import sys
import bisect
from collections import deque
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def seive():
	for i in range(2 * 2, 10 ** 5 + 1, 2):
		prime[i] = False
		sp[i] = 2
	p = 3
	while p * p <= 10 ** 5:
		if prime[p]:
			for j in range(p * p, 10 ** 5 + 1, p):
				if prime[j]:
					prime[j] = False
					sp[j] = p
		p += 2
n = int(ri())
prime = [True] * (10 ** 5 + 1)
sp = [i for i in range(10 ** 5 + 1)]
seive()
dic = {}
ite = 1
ans = [-1] * (n + 1)
for i in range(2, n + 1):
	if sp[i] in dic:
		ans[i] = dic[sp[i]]
	else:
		dic[sp[i]] = ite
		ans[i] = dic[sp[i]]
		ite += 1
print(*ans[2:])


n = int(input())
a = [0] * (n + 1)
cur = 0
for i in range(2, n + 1):
	if not a[i]:
		cur += 1
		for j in range(i, n + 1, i):
			a[j] = cur
print(*a[2:])


prime = [-1 for i in range(100005)]
p = 2
avail = 1
while p * p <= 100005:
	if prime[p] == -1:
		for i in range(p, 100005, p):
			if prime[i] == -1:
				prime[i] = avail
		avail += 1
	p += 1
for i in range(2, 100005):
	if prime[i] == -1:
		prime[i] = avail
		avail += 1
n = int(input())
print(*prime[2:n + 1])


n = int(input())
x = 2
prime = 0
p = [0] * (n + 1)
while x <= n:
	if p[x] == 0:
		prime += 1
		p[x] = prime
		for i in range(x + x, n + 1, x):
			p[i] = prime
	x += 1
print(*p[2:])


a = int(input())
z = [0] * (a + 1)
p = 1
for i in range(2, a + 1):
	j = i
	k = i
	n = 0
	while j <= a:
		if z[j] == 0:
			z[j] = p
			n = 1
		j += k
	if n:
		p += 1
		n = 0
print(*z[2:])


n = int(input())
curr = 0
ans = [0] * (n + 1)
for i in range(2, n + 1):
	if ans[i] == 0:
		curr += 1
		ans[i] = curr
		for j in range(i, n + 1, i):
			ans[j] = ans[i]
print(*ans[2:])


def funcao(num):
	res = [0] * (num + 1)
	i = 2
	a = 1
	while i <= num:
		if res[i] == 0:
			res[i] = a
			j = i * i
			while j <= num:
				res[j] = a
				j += i
			a += 1
		i += 1
	return res
num = int(input())
res = funcao(num)
res.remove(0)
res.remove(0)
print(*res)


n = int(input())
currentNum = 1
array = [0] * (n - 1)
for i in range(2, n + 1):
	if array[i - 2] == 0:
		for j in range(1, n // i + 1):
			if array[i * j - 2] == 0:
				array[i * j - 2] = currentNum
		currentNum += 1
print(*array)


n = int(input())
a = {}
c = 0
for i in range(2, n + 1):
	if i not in a:
		c += 1
		a[i] = c
		for j in range(2 * i, n + 1, i):
			a[j] = a[i]
for i in range(2, n + 1):
	print(a[i], end=' ')


def SieveOfEratosthenes(n):
	e = 0
	prime = [i - 1 for i in range(n + 1)]
	p = 2
	while p <= n:
		if prime[p] == p - 1:
			e += 1
			prime[p] = e
			for i in range(p * p, n + 1, p):
				prime[i] = e
		p += 1
	return prime
e = SieveOfEratosthenes(int(input()))
e = e[2:]
print(*e, sep=' ')


def __starting_point():
	n = int(input())
	a = [0 for i in range(n + 1)]
	m = 1
	for i in range(2, len(a)):
		if a[i] == 0:
			a[i] = m
			for j in range(i * i, len(a), i):
				a[j] = m
			m += 1
	print(' '.join([str(a[x]) for x in range(2, len(a))]))
__starting_point()


n = int(input())
curVal = 1
ans = [0 for x in range(n + 1)]
for i in range(2, n + 1):
	if ans[i] == 0:
		ans[i] = curVal
		for j in range(i * 2, n + 1, i):
			ans[j] = curVal
		curVal += 1
for q in ans[2:]:
	print(q, end=' ')
print('')


n = int(input())
nextcolor = 1
colors = [0 for i in range(n + 1)]
for i in range(2, n + 1):
	if colors[i] > 0:
		continue
	k = 1
	while k * i <= n:
		colors[k * i] = nextcolor
		k += 1
	nextcolor += 1
for i in range(2, n + 1):
	print(colors[i])


from sys import stdin
from collections import defaultdict
input = stdin.readline

def is_prime(n):
	if n < 2:
		return False
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	for i in range(3, n + 1):
		if i * i > n:
			break
		elif n % i == 0:
			return False
	return True
T = 1
for t in range(1, T + 1):
	n = int(input())
	res = [0 for x in range(n + 2)]
	count = 1
	for i in range(2, n + 1):
		if is_prime(i):
			res[i] = count
			count += 1
			for j in range(i * i, n + 1, i):
				res[j] = res[i]
	for i in range(2, n + 1):
		print(res[i], end=' ')


n = int(input())
vis = [0] * (n + 1)
count = 1
for i in range(2, n + 1):
	if vis[i] == 0:
		j = i
		while j < n + 1:
			vis[j] = count
			j += i
		count += 1
print(*vis[2:])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	pass

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def lts(l):
	s = ''.join(map(str, l))
	return s

def stl(s):
	l = list(s)
	return l

def sq(a, target, arr=[]):
	s = sum(arr)
	if s == target:
		return arr
	if s >= target:
		return
	for i in range(len(a)):
		n = a[i]
		remaining = a[i + 1:]
		ans = sq(remaining, target, arr + [n])
		if ans:
			return ans

def SieveOfEratosthenes(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
mod = int(1000000000.0) + 7

def ssinp():
	return input()

def iinp():
	return int(input())

def nninp():
	return map(int, input().split())

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

def p(xyz):
	print(xyz)

def p2(a, b):
	print(a, b)
import math

def Prime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return i
		return -1
n = iinp()
ans = []
ind = 1
for i in range(2, n + 1):
	x = Prime(i)
	if x == -1:
		ans.append(ind)
		ind += 1
	else:
		ans.append(ans[x - 2])
print(*ans)


n = int(input())
li = [0 for i in range(2, n + 1)]
p = 0
for i in range(2, n + 1):
	if li[i - 2] == 0:
		p += 1
		for j in range(i, n + 1, i):
			if li[j - 2] == 0:
				li[j - 2] = p
print(*li)


from sys import stdin
from math import gcd, sqrt
from collections import deque
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
hg = lambda x, y: (y + x - 1) // x * x
a = [0] * (10 ** 5 + 5)
n = I()
c = 0
for i in range(2, n + 1):
	if not a[i]:
		c += 1
		a[i] = c
		for j in range(i, n + 1, i):
			a[j] = a[i]
	print(a[i], end=' ')


def find_divisor(n):
	sqrt = int(n ** 0.5)
	for i in range(2, sqrt + 1):
		if n % i == 0:
			return i

def is_prime(n):
	sqrt = int(n ** 0.5)
	divisors = 0
	for i in range(1, sqrt + 1):
		if n % i == 0:
			divisors += 1
		if divisors > 1:
			return False
	return True
n = int(input())
numbers = [i for i in range(2, n + 1)]
result = [0] * len(numbers)
result[0] = '1'
dic = {}
dic[2] = 1
index = 2
for i in range(1, len(numbers)):
	if is_prime(numbers[i]):
		dic[numbers[i]] = index
		result[i] = str(index)
		index += 1
	else:
		result[i] = str(dic[find_divisor(numbers[i])])
print(' '.join(result))


n = int(input())
p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313]
a = [0] * (n - 1)
big = len(p) + 1
for i in range(2, n + 1):
	skip = False
	for j in range(65):
		if i % p[j] == 0:
			a[i - 2] = j + 1
			skip = True
			break
	if not skip:
		a[i - 2] = big
		big += 1
print(*a)


n = int(input())
mask = [0] * (n + 1)
cur = 1
for i in range(2, n + 1):
	if mask[i] != 0:
		continue
	ind = 1
	while i * ind <= n:
		if mask[i * ind] != 0:
			ind += 1
			continue
		mask[i * ind] = cur
		ind += 1
	cur += 1
for i in range(2, n + 1):
	print(mask[i], end=' ')


def sieve():
	vis = [1 for i in range(n + 1)]
	vis[0] = vis[1] = 0
	for i in range(n + 1):
		if vis[i]:
			prime.append(i)
			for j in range(i << 1, n + 1, i):
				vis[j] = 0
global prime
global n
n = eval(input())
prime = []
sieve()
a = [0 for i in range(n + 1)]
for i in range(len(prime)):
	now = prime[i]
	a[now] = i + 1
	val = now << 1
	while val <= n:
		a[val] = i + 1
		val += now
for i in range(2, n + 1):
	print(a[i], end=' ')


n = int(input()) + 1
(ls, c) = (['0'] * n, 1)
for i in range(2, n):
	if ls[i] != '0':
		continue
	for v in range(i, n, i):
		ls[v] = str(c)
	c += 1
print(' '.join(ls[2:]))


P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859, 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957, 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071, 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393, 11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491, 11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933, 11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923, 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967, 13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083, 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221, 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447, 14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551, 14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831, 14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939, 14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073, 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149, 15161, 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269, 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559, 15569, 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649, 15661, 15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859, 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959, 15971, 15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069, 16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301, 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417, 16421, 16427, 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747, 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871, 16879, 16883, 16889, 16901, 16903, 16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993, 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077, 17093, 17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191, 17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317, 17321, 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389, 17393, 17401, 17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477, 17483, 17489, 17491, 17497, 17509, 17519, 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599, 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713, 17729, 17737, 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827, 17837, 17839, 17851, 17863, 17881, 17891, 17903, 17909, 17911, 17921, 17923, 17929, 17939, 17957, 17959, 17971, 17977, 17981, 17987, 17989, 18013, 18041, 18043, 18047, 18049, 18059, 18061, 18077, 18089, 18097, 18119, 18121, 18127, 18131, 18133, 18143, 18149, 18169, 18181, 18191, 18199, 18211, 18217, 18223, 18229, 18233, 18251, 18253, 18257, 18269, 18287, 18289, 18301, 18307, 18311, 18313, 18329, 18341, 18353, 18367, 18371, 18379, 18397, 18401, 18413, 18427, 18433, 18439, 18443, 18451, 18457, 18461, 18481, 18493, 18503, 18517, 18521, 18523, 18539, 18541, 18553, 18583, 18587, 18593, 18617, 18637, 18661, 18671, 18679, 18691, 18701, 18713, 18719, 18731, 18743, 18749, 18757, 18773, 18787, 18793, 18797, 18803, 18839, 18859, 18869, 18899, 18911, 18913, 18917, 18919, 18947, 18959, 18973, 18979, 19001, 19009, 19013, 19031, 19037, 19051, 19069, 19073, 19079, 19081, 19087, 19121, 19139, 19141, 19157, 19163, 19181, 19183, 19207, 19211, 19213, 19219, 19231, 19237, 19249, 19259, 19267, 19273, 19289, 19301, 19309, 19319, 19333, 19373, 19379, 19381, 19387, 19391, 19403, 19417, 19421, 19423, 19427, 19429, 19433, 19441, 19447, 19457, 19463, 19469, 19471, 19477, 19483, 19489, 19501, 19507, 19531, 19541, 19543, 19553, 19559, 19571, 19577, 19583, 19597, 19603, 19609, 19661, 19681, 19687, 19697, 19699, 19709, 19717, 19727, 19739, 19751, 19753, 19759, 19763, 19777, 19793, 19801, 19813, 19819, 19841, 19843, 19853, 19861, 19867, 19889, 19891, 19913, 19919, 19927, 19937, 19949, 19961, 19963, 19973, 19979, 19991, 19993, 19997, 20011, 20021, 20023, 20029, 20047, 20051, 20063, 20071, 20089, 20101, 20107, 20113, 20117, 20123, 20129, 20143, 20147, 20149, 20161, 20173, 20177, 20183, 20201, 20219, 20231, 20233, 20249, 20261, 20269, 20287, 20297, 20323, 20327, 20333, 20341, 20347, 20353, 20357, 20359, 20369, 20389, 20393, 20399, 20407, 20411, 20431, 20441, 20443, 20477, 20479, 20483, 20507, 20509, 20521, 20533, 20543, 20549, 20551, 20563, 20593, 20599, 20611, 20627, 20639, 20641, 20663, 20681, 20693, 20707, 20717, 20719, 20731, 20743, 20747, 20749, 20753, 20759, 20771, 20773, 20789, 20807, 20809, 20849, 20857, 20873, 20879, 20887, 20897, 20899, 20903, 20921, 20929, 20939, 20947, 20959, 20963, 20981, 20983, 21001, 21011, 21013, 21017, 21019, 21023, 21031, 21059, 21061, 21067, 21089, 21101, 21107, 21121, 21139, 21143, 21149, 21157, 21163, 21169, 21179, 21187, 21191, 21193, 21211, 21221, 21227, 21247, 21269, 21277, 21283, 21313, 21317, 21319, 21323, 21341, 21347, 21377, 21379, 21383, 21391, 21397, 21401, 21407, 21419, 21433, 21467, 21481, 21487, 21491, 21493, 21499, 21503, 21517, 21521, 21523, 21529, 21557, 21559, 21563, 21569, 21577, 21587, 21589, 21599, 21601, 21611, 21613, 21617, 21647, 21649, 21661, 21673, 21683, 21701, 21713, 21727, 21737, 21739, 21751, 21757, 21767, 21773, 21787, 21799, 21803, 21817, 21821, 21839, 21841, 21851, 21859, 21863, 21871, 21881, 21893, 21911, 21929, 21937, 21943, 21961, 21977, 21991, 21997, 22003, 22013, 22027, 22031, 22037, 22039, 22051, 22063, 22067, 22073, 22079, 22091, 22093, 22109, 22111, 22123, 22129, 22133, 22147, 22153, 22157, 22159, 22171, 22189, 22193, 22229, 22247, 22259, 22271, 22273, 22277, 22279, 22283, 22291, 22303, 22307, 22343, 22349, 22367, 22369, 22381, 22391, 22397, 22409, 22433, 22441, 22447, 22453, 22469, 22481, 22483, 22501, 22511, 22531, 22541, 22543, 22549, 22567, 22571, 22573, 22613, 22619, 22621, 22637, 22639, 22643, 22651, 22669, 22679, 22691, 22697, 22699, 22709, 22717, 22721, 22727, 22739, 22741, 22751, 22769, 22777, 22783, 22787, 22807, 22811, 22817, 22853, 22859, 22861, 22871, 22877, 22901, 22907, 22921, 22937, 22943, 22961, 22963, 22973, 22993, 23003, 23011, 23017, 23021, 23027, 23029, 23039, 23041, 23053, 23057, 23059, 23063, 23071, 23081, 23087, 23099, 23117, 23131, 23143, 23159, 23167, 23173, 23189, 23197, 23201, 23203, 23209, 23227, 23251, 23269, 23279, 23291, 23293, 23297, 23311, 23321, 23327, 23333, 23339, 23357, 23369, 23371, 23399, 23417, 23431, 23447, 23459, 23473, 23497, 23509, 23531, 23537, 23539, 23549, 23557, 23561, 23563, 23567, 23581, 23593, 23599, 23603, 23609, 23623, 23627, 23629, 23633, 23663, 23669, 23671, 23677, 23687, 23689, 23719, 23741, 23743, 23747, 23753, 23761, 23767, 23773, 23789, 23801, 23813, 23819, 23827, 23831, 23833, 23857, 23869, 23873, 23879, 23887, 23893, 23899, 23909, 23911, 23917, 23929, 23957, 23971, 23977, 23981, 23993, 24001, 24007, 24019, 24023, 24029, 24043, 24049, 24061, 24071, 24077, 24083, 24091, 24097, 24103, 24107, 24109, 24113, 24121, 24133, 24137, 24151, 24169, 24179, 24181, 24197, 24203, 24223, 24229, 24239, 24247, 24251, 24281, 24317, 24329, 24337, 24359, 24371, 24373, 24379, 24391, 24407, 24413, 24419, 24421, 24439, 24443, 24469, 24473, 24481, 24499, 24509, 24517, 24527, 24533, 24547, 24551, 24571, 24593, 24611, 24623, 24631, 24659, 24671, 24677, 24683, 24691, 24697, 24709, 24733, 24749, 24763, 24767, 24781, 24793, 24799, 24809, 24821, 24841, 24847, 24851, 24859, 24877, 24889, 24907, 24917, 24919, 24923, 24943, 24953, 24967, 24971, 24977, 24979, 24989, 25013, 25031, 25033, 25037, 25057, 25073, 25087, 25097, 25111, 25117, 25121, 25127, 25147, 25153, 25163, 25169, 25171, 25183, 25189, 25219, 25229, 25237, 25243, 25247, 25253, 25261, 25301, 25303, 25307, 25309, 25321, 25339, 25343, 25349, 25357, 25367, 25373, 25391, 25409, 25411, 25423, 25439, 25447, 25453, 25457, 25463, 25469, 25471, 25523, 25537, 25541, 25561, 25577, 25579, 25583, 25589, 25601, 25603, 25609, 25621, 25633, 25639, 25643, 25657, 25667, 25673, 25679, 25693, 25703, 25717, 25733, 25741, 25747, 25759, 25763, 25771, 25793, 25799, 25801, 25819, 25841, 25847, 25849, 25867, 25873, 25889, 25903, 25913, 25919, 25931, 25933, 25939, 25943, 25951, 25969, 25981, 25997, 25999, 26003, 26017, 26021, 26029, 26041, 26053, 26083, 26099, 26107, 26111, 26113, 26119, 26141, 26153, 26161, 26171, 26177, 26183, 26189, 26203, 26209, 26227, 26237, 26249, 26251, 26261, 26263, 26267, 26293, 26297, 26309, 26317, 26321, 26339, 26347, 26357, 26371, 26387, 26393, 26399, 26407, 26417, 26423, 26431, 26437, 26449, 26459, 26479, 26489, 26497, 26501, 26513, 26539, 26557, 26561, 26573, 26591, 26597, 26627, 26633, 26641, 26647, 26669, 26681, 26683, 26687, 26693, 26699, 26701, 26711, 26713, 26717, 26723, 26729, 26731, 26737, 26759, 26777, 26783, 26801, 26813, 26821, 26833, 26839, 26849, 26861, 26863, 26879, 26881, 26891, 26893, 26903, 26921, 26927, 26947, 26951, 26953, 26959, 26981, 26987, 26993, 27011, 27017, 27031, 27043, 27059, 27061, 27067, 27073, 27077, 27091, 27103, 27107, 27109, 27127, 27143, 27179, 27191, 27197, 27211, 27239, 27241, 27253, 27259, 27271, 27277, 27281, 27283, 27299, 27329, 27337, 27361, 27367, 27397, 27407, 27409, 27427, 27431, 27437, 27449, 27457, 27479, 27481, 27487, 27509, 27527, 27529, 27539, 27541, 27551, 27581, 27583, 27611, 27617, 27631, 27647, 27653, 27673, 27689, 27691, 27697, 27701, 27733, 27737, 27739, 27743, 27749, 27751, 27763, 27767, 27773, 27779, 27791, 27793, 27799, 27803, 27809, 27817, 27823, 27827, 27847, 27851, 27883, 27893, 27901, 27917, 27919, 27941, 27943, 27947, 27953, 27961, 27967, 27983, 27997, 28001, 28019, 28027, 28031, 28051, 28057, 28069, 28081, 28087, 28097, 28099, 28109, 28111, 28123, 28151, 28163, 28181, 28183, 28201, 28211, 28219, 28229, 28277, 28279, 28283, 28289, 28297, 28307, 28309, 28319, 28349, 28351, 28387, 28393, 28403, 28409, 28411, 28429, 28433, 28439, 28447, 28463, 28477, 28493, 28499, 28513, 28517, 28537, 28541, 28547, 28549, 28559, 28571, 28573, 28579, 28591, 28597, 28603, 28607, 28619, 28621, 28627, 28631, 28643, 28649, 28657, 28661, 28663, 28669, 28687, 28697, 28703, 28711, 28723, 28729, 28751, 28753, 28759, 28771, 28789, 28793, 28807, 28813, 28817, 28837, 28843, 28859, 28867, 28871, 28879, 28901, 28909, 28921, 28927, 28933, 28949, 28961, 28979, 29009, 29017, 29021, 29023, 29027, 29033, 29059, 29063, 29077, 29101, 29123, 29129, 29131, 29137, 29147, 29153, 29167, 29173, 29179, 29191, 29201, 29207, 29209, 29221, 29231, 29243, 29251, 29269, 29287, 29297, 29303, 29311, 29327, 29333, 29339, 29347, 29363, 29383, 29387, 29389, 29399, 29401, 29411, 29423, 29429, 29437, 29443, 29453, 29473, 29483, 29501, 29527, 29531, 29537, 29567, 29569, 29573, 29581, 29587, 29599, 29611, 29629, 29633, 29641, 29663, 29669, 29671, 29683, 29717, 29723, 29741, 29753, 29759, 29761, 29789, 29803, 29819, 29833, 29837, 29851, 29863, 29867, 29873, 29879, 29881, 29917, 29921, 29927, 29947, 29959, 29983, 29989, 30011, 30013, 30029, 30047, 30059, 30071, 30089, 30091, 30097, 30103, 30109, 30113, 30119, 30133, 30137, 30139, 30161, 30169, 30181, 30187, 30197, 30203, 30211, 30223, 30241, 30253, 30259, 30269, 30271, 30293, 30307, 30313, 30319, 30323, 30341, 30347, 30367, 30389, 30391, 30403, 30427, 30431, 30449, 30467, 30469, 30491, 30493, 30497, 30509, 30517, 30529, 30539, 30553, 30557, 30559, 30577, 30593, 30631, 30637, 30643, 30649, 30661, 30671, 30677, 30689, 30697, 30703, 30707, 30713, 30727, 30757, 30763, 30773, 30781, 30803, 30809, 30817, 30829, 30839, 30841, 30851, 30853, 30859, 30869, 30871, 30881, 30893, 30911, 30931, 30937, 30941, 30949, 30971, 30977, 30983, 31013, 31019, 31033, 31039, 31051, 31063, 31069, 31079, 31081, 31091, 31121, 31123, 31139, 31147, 31151, 31153, 31159, 31177, 31181, 31183, 31189, 31193, 31219, 31223, 31231, 31237, 31247, 31249, 31253, 31259, 31267, 31271, 31277, 31307, 31319, 31321, 31327, 31333, 31337, 31357, 31379, 31387, 31391, 31393, 31397, 31469, 31477, 31481, 31489, 31511, 31513, 31517, 31531, 31541, 31543, 31547, 31567, 31573, 31583, 31601, 31607, 31627, 31643, 31649, 31657, 31663, 31667, 31687, 31699, 31721, 31723, 31727, 31729, 31741, 31751, 31769, 31771, 31793, 31799, 31817, 31847, 31849, 31859, 31873, 31883, 31891, 31907, 31957, 31963, 31973, 31981, 31991, 32003, 32009, 32027, 32029, 32051, 32057, 32059, 32063, 32069, 32077, 32083, 32089, 32099, 32117, 32119, 32141, 32143, 32159, 32173, 32183, 32189, 32191, 32203, 32213, 32233, 32237, 32251, 32257, 32261, 32297, 32299, 32303, 32309, 32321, 32323, 32327, 32341, 32353, 32359, 32363, 32369, 32371, 32377, 32381, 32401, 32411, 32413, 32423, 32429, 32441, 32443, 32467, 32479, 32491, 32497, 32503, 32507, 32531, 32533, 32537, 32561, 32563, 32569, 32573, 32579, 32587, 32603, 32609, 32611, 32621, 32633, 32647, 32653, 32687, 32693, 32707, 32713, 32717, 32719, 32749, 32771, 32779, 32783, 32789, 32797, 32801, 32803, 32831, 32833, 32839, 32843, 32869, 32887, 32909, 32911, 32917, 32933, 32939, 32941, 32957, 32969, 32971, 32983, 32987, 32993, 32999, 33013, 33023, 33029, 33037, 33049, 33053, 33071, 33073, 33083, 33091, 33107, 33113, 33119, 33149, 33151, 33161, 33179, 33181, 33191, 33199, 33203, 33211, 33223, 33247, 33287, 33289, 33301, 33311, 33317, 33329, 33331, 33343, 33347, 33349, 33353, 33359, 33377, 33391, 33403, 33409, 33413, 33427, 33457, 33461, 33469, 33479, 33487, 33493, 33503, 33521, 33529, 33533, 33547, 33563, 33569, 33577, 33581, 33587, 33589, 33599, 33601, 33613, 33617, 33619, 33623, 33629, 33637, 33641, 33647, 33679, 33703, 33713, 33721, 33739, 33749, 33751, 33757, 33767, 33769, 33773, 33791, 33797, 33809, 33811, 33827, 33829, 33851, 33857, 33863, 33871, 33889, 33893, 33911, 33923, 33931, 33937, 33941, 33961, 33967, 33997, 34019, 34031, 34033, 34039, 34057, 34061, 34123, 34127, 34129, 34141, 34147, 34157, 34159, 34171, 34183, 34211, 34213, 34217, 34231, 34253, 34259, 34261, 34267, 34273, 34283, 34297, 34301, 34303, 34313, 34319, 34327, 34337, 34351, 34361, 34367, 34369, 34381, 34403, 34421, 34429, 34439, 34457, 34469, 34471, 34483, 34487, 34499, 34501, 34511, 34513, 34519, 34537, 34543, 34549, 34583, 34589, 34591, 34603, 34607, 34613, 34631, 34649, 34651, 34667, 34673, 34679, 34687, 34693, 34703, 34721, 34729, 34739, 34747, 34757, 34759, 34763, 34781, 34807, 34819, 34841, 34843, 34847, 34849, 34871, 34877, 34883, 34897, 34913, 34919, 34939, 34949, 34961, 34963, 34981, 35023, 35027, 35051, 35053, 35059, 35069, 35081, 35083, 35089, 35099, 35107, 35111, 35117, 35129, 35141, 35149, 35153, 35159, 35171, 35201, 35221, 35227, 35251, 35257, 35267, 35279, 35281, 35291, 35311, 35317, 35323, 35327, 35339, 35353, 35363, 35381, 35393, 35401, 35407, 35419, 35423, 35437, 35447, 35449, 35461, 35491, 35507, 35509, 35521, 35527, 35531, 35533, 35537, 35543, 35569, 35573, 35591, 35593, 35597, 35603, 35617, 35671, 35677, 35729, 35731, 35747, 35753, 35759, 35771, 35797, 35801, 35803, 35809, 35831, 35837, 35839, 35851, 35863, 35869, 35879, 35897, 35899, 35911, 35923, 35933, 35951, 35963, 35969, 35977, 35983, 35993, 35999, 36007, 36011, 36013, 36017, 36037, 36061, 36067, 36073, 36083, 36097, 36107, 36109, 36131, 36137, 36151, 36161, 36187, 36191, 36209, 36217, 36229, 36241, 36251, 36263, 36269, 36277, 36293, 36299, 36307, 36313, 36319, 36341, 36343, 36353, 36373, 36383, 36389, 36433, 36451, 36457, 36467, 36469, 36473, 36479, 36493, 36497, 36523, 36527, 36529, 36541, 36551, 36559, 36563, 36571, 36583, 36587, 36599, 36607, 36629, 36637, 36643, 36653, 36671, 36677, 36683, 36691, 36697, 36709, 36713, 36721, 36739, 36749, 36761, 36767, 36779, 36781, 36787, 36791, 36793, 36809, 36821, 36833, 36847, 36857, 36871, 36877, 36887, 36899, 36901, 36913, 36919, 36923, 36929, 36931, 36943, 36947, 36973, 36979, 36997, 37003, 37013, 37019, 37021, 37039, 37049, 37057, 37061, 37087, 37097, 37117, 37123, 37139, 37159, 37171, 37181, 37189, 37199, 37201, 37217, 37223, 37243, 37253, 37273, 37277, 37307, 37309, 37313, 37321, 37337, 37339, 37357, 37361, 37363, 37369, 37379, 37397, 37409, 37423, 37441, 37447, 37463, 37483, 37489, 37493, 37501, 37507, 37511, 37517, 37529, 37537, 37547, 37549, 37561, 37567, 37571, 37573, 37579, 37589, 37591, 37607, 37619, 37633, 37643, 37649, 37657, 37663, 37691, 37693, 37699, 37717, 37747, 37781, 37783, 37799, 37811, 37813, 37831, 37847, 37853, 37861, 37871, 37879, 37889, 37897, 37907, 37951, 37957, 37963, 37967, 37987, 37991, 37993, 37997, 38011, 38039, 38047, 38053, 38069, 38083, 38113, 38119, 38149, 38153, 38167, 38177, 38183, 38189, 38197, 38201, 38219, 38231, 38237, 38239, 38261, 38273, 38281, 38287, 38299, 38303, 38317, 38321, 38327, 38329, 38333, 38351, 38371, 38377, 38393, 38431, 38447, 38449, 38453, 38459, 38461, 38501, 38543, 38557, 38561, 38567, 38569, 38593, 38603, 38609, 38611, 38629, 38639, 38651, 38653, 38669, 38671, 38677, 38693, 38699, 38707, 38711, 38713, 38723, 38729, 38737, 38747, 38749, 38767, 38783, 38791, 38803, 38821, 38833, 38839, 38851, 38861, 38867, 38873, 38891, 38903, 38917, 38921, 38923, 38933, 38953, 38959, 38971, 38977, 38993, 39019, 39023, 39041, 39043, 39047, 39079, 39089, 39097, 39103, 39107, 39113, 39119, 39133, 39139, 39157, 39161, 39163, 39181, 39191, 39199, 39209, 39217, 39227, 39229, 39233, 39239, 39241, 39251, 39293, 39301, 39313, 39317, 39323, 39341, 39343, 39359, 39367, 39371, 39373, 39383, 39397, 39409, 39419, 39439, 39443, 39451, 39461, 39499, 39503, 39509, 39511, 39521, 39541, 39551, 39563, 39569, 39581, 39607, 39619, 39623, 39631, 39659, 39667, 39671, 39679, 39703, 39709, 39719, 39727, 39733, 39749, 39761, 39769, 39779, 39791, 39799, 39821, 39827, 39829, 39839, 39841, 39847, 39857, 39863, 39869, 39877, 39883, 39887, 39901, 39929, 39937, 39953, 39971, 39979, 39983, 39989, 40009, 40013, 40031, 40037, 40039, 40063, 40087, 40093, 40099, 40111, 40123, 40127, 40129, 40151, 40153, 40163, 40169, 40177, 40189, 40193, 40213, 40231, 40237, 40241, 40253, 40277, 40283, 40289, 40343, 40351, 40357, 40361, 40387, 40423, 40427, 40429, 40433, 40459, 40471, 40483, 40487, 40493, 40499, 40507, 40519, 40529, 40531, 40543, 40559, 40577, 40583, 40591, 40597, 40609, 40627, 40637, 40639, 40693, 40697, 40699, 40709, 40739, 40751, 40759, 40763, 40771, 40787, 40801, 40813, 40819, 40823, 40829, 40841, 40847, 40849, 40853, 40867, 40879, 40883, 40897, 40903, 40927, 40933, 40939, 40949, 40961, 40973, 40993, 41011, 41017, 41023, 41039, 41047, 41051, 41057, 41077, 41081, 41113, 41117, 41131, 41141, 41143, 41149, 41161, 41177, 41179, 41183, 41189, 41201, 41203, 41213, 41221, 41227, 41231, 41233, 41243, 41257, 41263, 41269, 41281, 41299, 41333, 41341, 41351, 41357, 41381, 41387, 41389, 41399, 41411, 41413, 41443, 41453, 41467, 41479, 41491, 41507, 41513, 41519, 41521, 41539, 41543, 41549, 41579, 41593, 41597, 41603, 41609, 41611, 41617, 41621, 41627, 41641, 41647, 41651, 41659, 41669, 41681, 41687, 41719, 41729, 41737, 41759, 41761, 41771, 41777, 41801, 41809, 41813, 41843, 41849, 41851, 41863, 41879, 41887, 41893, 41897, 41903, 41911, 41927, 41941, 41947, 41953, 41957, 41959, 41969, 41981, 41983, 41999, 42013, 42017, 42019, 42023, 42043, 42061, 42071, 42073, 42083, 42089, 42101, 42131, 42139, 42157, 42169, 42179, 42181, 42187, 42193, 42197, 42209, 42221, 42223, 42227, 42239, 42257, 42281, 42283, 42293, 42299, 42307, 42323, 42331, 42337, 42349, 42359, 42373, 42379, 42391, 42397, 42403, 42407, 42409, 42433, 42437, 42443, 42451, 42457, 42461, 42463, 42467, 42473, 42487, 42491, 42499, 42509, 42533, 42557, 42569, 42571, 42577, 42589, 42611, 42641, 42643, 42649, 42667, 42677, 42683, 42689, 42697, 42701, 42703, 42709, 42719, 42727, 42737, 42743, 42751, 42767, 42773, 42787, 42793, 42797, 42821, 42829, 42839, 42841, 42853, 42859, 42863, 42899, 42901, 42923, 42929, 42937, 42943, 42953, 42961, 42967, 42979, 42989, 43003, 43013, 43019, 43037, 43049, 43051, 43063, 43067, 43093, 43103, 43117, 43133, 43151, 43159, 43177, 43189, 43201, 43207, 43223, 43237, 43261, 43271, 43283, 43291, 43313, 43319, 43321, 43331, 43391, 43397, 43399, 43403, 43411, 43427, 43441, 43451, 43457, 43481, 43487, 43499, 43517, 43541, 43543, 43573, 43577, 43579, 43591, 43597, 43607, 43609, 43613, 43627, 43633, 43649, 43651, 43661, 43669, 43691, 43711, 43717, 43721, 43753, 43759, 43777, 43781, 43783, 43787, 43789, 43793, 43801, 43853, 43867, 43889, 43891, 43913, 43933, 43943, 43951, 43961, 43963, 43969, 43973, 43987, 43991, 43997, 44017, 44021, 44027, 44029, 44041, 44053, 44059, 44071, 44087, 44089, 44101, 44111, 44119, 44123, 44129, 44131, 44159, 44171, 44179, 44189, 44201, 44203, 44207, 44221, 44249, 44257, 44263, 44267, 44269, 44273, 44279, 44281, 44293, 44351, 44357, 44371, 44381, 44383, 44389, 44417, 44449, 44453, 44483, 44491, 44497, 44501, 44507, 44519, 44531, 44533, 44537, 44543, 44549, 44563, 44579, 44587, 44617, 44621, 44623, 44633, 44641, 44647, 44651, 44657, 44683, 44687, 44699, 44701, 44711, 44729, 44741, 44753, 44771, 44773, 44777, 44789, 44797, 44809, 44819, 44839, 44843, 44851, 44867, 44879, 44887, 44893, 44909, 44917, 44927, 44939, 44953, 44959, 44963, 44971, 44983, 44987, 45007, 45013, 45053, 45061, 45077, 45083, 45119, 45121, 45127, 45131, 45137, 45139, 45161, 45179, 45181, 45191, 45197, 45233, 45247, 45259, 45263, 45281, 45289, 45293, 45307, 45317, 45319, 45329, 45337, 45341, 45343, 45361, 45377, 45389, 45403, 45413, 45427, 45433, 45439, 45481, 45491, 45497, 45503, 45523, 45533, 45541, 45553, 45557, 45569, 45587, 45589, 45599, 45613, 45631, 45641, 45659, 45667, 45673, 45677, 45691, 45697, 45707, 45737, 45751, 45757, 45763, 45767, 45779, 45817, 45821, 45823, 45827, 45833, 45841, 45853, 45863, 45869, 45887, 45893, 45943, 45949, 45953, 45959, 45971, 45979, 45989, 46021, 46027, 46049, 46051, 46061, 46073, 46091, 46093, 46099, 46103, 46133, 46141, 46147, 46153, 46171, 46181, 46183, 46187, 46199, 46219, 46229, 46237, 46261, 46271, 46273, 46279, 46301, 46307, 46309, 46327, 46337, 46349, 46351, 46381, 46399, 46411, 46439, 46441, 46447, 46451, 46457, 46471, 46477, 46489, 46499, 46507, 46511, 46523, 46549, 46559, 46567, 46573, 46589, 46591, 46601, 46619, 46633, 46639, 46643, 46649, 46663, 46679, 46681, 46687, 46691, 46703, 46723, 46727, 46747, 46751, 46757, 46769, 46771, 46807, 46811, 46817, 46819, 46829, 46831, 46853, 46861, 46867, 46877, 46889, 46901, 46919, 46933, 46957, 46993, 46997, 47017, 47041, 47051, 47057, 47059, 47087, 47093, 47111, 47119, 47123, 47129, 47137, 47143, 47147, 47149, 47161, 47189, 47207, 47221, 47237, 47251, 47269, 47279, 47287, 47293, 47297, 47303, 47309, 47317, 47339, 47351, 47353, 47363, 47381, 47387, 47389, 47407, 47417, 47419, 47431, 47441, 47459, 47491, 47497, 47501, 47507, 47513, 47521, 47527, 47533, 47543, 47563, 47569, 47581, 47591, 47599, 47609, 47623, 47629, 47639, 47653, 47657, 47659, 47681, 47699, 47701, 47711, 47713, 47717, 47737, 47741, 47743, 47777, 47779, 47791, 47797, 47807, 47809, 47819, 47837, 47843, 47857, 47869, 47881, 47903, 47911, 47917, 47933, 47939, 47947, 47951, 47963, 47969, 47977, 47981, 48017, 48023, 48029, 48049, 48073, 48079, 48091, 48109, 48119, 48121, 48131, 48157, 48163, 48179, 48187, 48193, 48197, 48221, 48239, 48247, 48259, 48271, 48281, 48299, 48311, 48313, 48337, 48341, 48353, 48371, 48383, 48397, 48407, 48409, 48413, 48437, 48449, 48463, 48473, 48479, 48481, 48487, 48491, 48497, 48523, 48527, 48533, 48539, 48541, 48563, 48571, 48589, 48593, 48611, 48619, 48623, 48647, 48649, 48661, 48673, 48677, 48679, 48731, 48733, 48751, 48757, 48761, 48767, 48779, 48781, 48787, 48799, 48809, 48817, 48821, 48823, 48847, 48857, 48859, 48869, 48871, 48883, 48889, 48907, 48947, 48953, 48973, 48989, 48991, 49003, 49009, 49019, 49031, 49033, 49037, 49043, 49057, 49069, 49081, 49103, 49109, 49117, 49121, 49123, 49139, 49157, 49169, 49171, 49177, 49193, 49199, 49201, 49207, 49211, 49223, 49253, 49261, 49277, 49279, 49297, 49307, 49331, 49333, 49339, 49363, 49367, 49369, 49391, 49393, 49409, 49411, 49417, 49429, 49433, 49451, 49459, 49463, 49477, 49481, 49499, 49523, 49529, 49531, 49537, 49547, 49549, 49559, 49597, 49603, 49613, 49627, 49633, 49639, 49663, 49667, 49669, 49681, 49697, 49711, 49727, 49739, 49741, 49747, 49757, 49783, 49787, 49789, 49801, 49807, 49811, 49823, 49831, 49843, 49853, 49871, 49877, 49891, 49919, 49921, 49927, 49937, 49939, 49943, 49957, 49991, 49993, 49999, 50021, 50023, 50033, 50047, 50051, 50053, 50069, 50077, 50087, 50093, 50101, 50111, 50119, 50123, 50129, 50131, 50147, 50153, 50159, 50177, 50207, 50221, 50227, 50231, 50261, 50263, 50273, 50287, 50291, 50311, 50321, 50329, 50333, 50341, 50359, 50363, 50377, 50383, 50387, 50411, 50417, 50423, 50441, 50459, 50461, 50497, 50503, 50513, 50527, 50539, 50543, 50549, 50551, 50581, 50587, 50591, 50593, 50599, 50627, 50647, 50651, 50671, 50683, 50707, 50723, 50741, 50753, 50767, 50773, 50777, 50789, 50821, 50833, 50839, 50849, 50857, 50867, 50873, 50891, 50893, 50909, 50923, 50929, 50951, 50957, 50969, 50971, 50989, 50993, 51001, 51031, 51043, 51047, 51059, 51061, 51071, 51109, 51131, 51133, 51137, 51151, 51157, 51169, 51193, 51197, 51199, 51203, 51217, 51229, 51239, 51241, 51257, 51263, 51283, 51287, 51307, 51329, 51341, 51343, 51347, 51349, 51361, 51383, 51407, 51413, 51419, 51421, 51427, 51431, 51437, 51439, 51449, 51461, 51473, 51479, 51481, 51487, 51503, 51511, 51517, 51521, 51539, 51551, 51563, 51577, 51581, 51593, 51599, 51607, 51613, 51631, 51637, 51647, 51659, 51673, 51679, 51683, 51691, 51713, 51719, 51721, 51749, 51767, 51769, 51787, 51797, 51803, 51817, 51827, 51829, 51839, 51853, 51859, 51869, 51871, 51893, 51899, 51907, 51913, 51929, 51941, 51949, 51971, 51973, 51977, 51991, 52009, 52021, 52027, 52051, 52057, 52067, 52069, 52081, 52103, 52121, 52127, 52147, 52153, 52163, 52177, 52181, 52183, 52189, 52201, 52223, 52237, 52249, 52253, 52259, 52267, 52289, 52291, 52301, 52313, 52321, 52361, 52363, 52369, 52379, 52387, 52391, 52433, 52453, 52457, 52489, 52501, 52511, 52517, 52529, 52541, 52543, 52553, 52561, 52567, 52571, 52579, 52583, 52609, 52627, 52631, 52639, 52667, 52673, 52691, 52697, 52709, 52711, 52721, 52727, 52733, 52747, 52757, 52769, 52783, 52807, 52813, 52817, 52837, 52859, 52861, 52879, 52883, 52889, 52901, 52903, 52919, 52937, 52951, 52957, 52963, 52967, 52973, 52981, 52999, 53003, 53017, 53047, 53051, 53069, 53077, 53087, 53089, 53093, 53101, 53113, 53117, 53129, 53147, 53149, 53161, 53171, 53173, 53189, 53197, 53201, 53231, 53233, 53239, 53267, 53269, 53279, 53281, 53299, 53309, 53323, 53327, 53353, 53359, 53377, 53381, 53401, 53407, 53411, 53419, 53437, 53441, 53453, 53479, 53503, 53507, 53527, 53549, 53551, 53569, 53591, 53593, 53597, 53609, 53611, 53617, 53623, 53629, 53633, 53639, 53653, 53657, 53681, 53693, 53699, 53717, 53719, 53731, 53759, 53773, 53777, 53783, 53791, 53813, 53819, 53831, 53849, 53857, 53861, 53881, 53887, 53891, 53897, 53899, 53917, 53923, 53927, 53939, 53951, 53959, 53987, 53993, 54001, 54011, 54013, 54037, 54049, 54059, 54083, 54091, 54101, 54121, 54133, 54139, 54151, 54163, 54167, 54181, 54193, 54217, 54251, 54269, 54277, 54287, 54293, 54311, 54319, 54323, 54331, 54347, 54361, 54367, 54371, 54377, 54401, 54403, 54409, 54413, 54419, 54421, 54437, 54443, 54449, 54469, 54493, 54497, 54499, 54503, 54517, 54521, 54539, 54541, 54547, 54559, 54563, 54577, 54581, 54583, 54601, 54617, 54623, 54629, 54631, 54647, 54667, 54673, 54679, 54709, 54713, 54721, 54727, 54751, 54767, 54773, 54779, 54787, 54799, 54829, 54833, 54851, 54869, 54877, 54881, 54907, 54917, 54919, 54941, 54949, 54959, 54973, 54979, 54983, 55001, 55009, 55021, 55049, 55051, 55057, 55061, 55073, 55079, 55103, 55109, 55117, 55127, 55147, 55163, 55171, 55201, 55207, 55213, 55217, 55219, 55229, 55243, 55249, 55259, 55291, 55313, 55331, 55333, 55337, 55339, 55343, 55351, 55373, 55381, 55399, 55411, 55439, 55441, 55457, 55469, 55487, 55501, 55511, 55529, 55541, 55547, 55579, 55589, 55603, 55609, 55619, 55621, 55631, 55633, 55639, 55661, 55663, 55667, 55673, 55681, 55691, 55697, 55711, 55717, 55721, 55733, 55763, 55787, 55793, 55799, 55807, 55813, 55817, 55819, 55823, 55829, 55837, 55843, 55849, 55871, 55889, 55897, 55901, 55903, 55921, 55927, 55931, 55933, 55949, 55967, 55987, 55997, 56003, 56009, 56039, 56041, 56053, 56081, 56087, 56093, 56099, 56101, 56113, 56123, 56131, 56149, 56167, 56171, 56179, 56197, 56207, 56209, 56237, 56239, 56249, 56263, 56267, 56269, 56299, 56311, 56333, 56359, 56369, 56377, 56383, 56393, 56401, 56417, 56431, 56437, 56443, 56453, 56467, 56473, 56477, 56479, 56489, 56501, 56503, 56509, 56519, 56527, 56531, 56533, 56543, 56569, 56591, 56597, 56599, 56611, 56629, 56633, 56659, 56663, 56671, 56681, 56687, 56701, 56711, 56713, 56731, 56737, 56747, 56767, 56773, 56779, 56783, 56807, 56809, 56813, 56821, 56827, 56843, 56857, 56873, 56891, 56893, 56897, 56909, 56911, 56921, 56923, 56929, 56941, 56951, 56957, 56963, 56983, 56989, 56993, 56999, 57037, 57041, 57047, 57059, 57073, 57077, 57089, 57097, 57107, 57119, 57131, 57139, 57143, 57149, 57163, 57173, 57179, 57191, 57193, 57203, 57221, 57223, 57241, 57251, 57259, 57269, 57271, 57283, 57287, 57301, 57329, 57331, 57347, 57349, 57367, 57373, 57383, 57389, 57397, 57413, 57427, 57457, 57467, 57487, 57493, 57503, 57527, 57529, 57557, 57559, 57571, 57587, 57593, 57601, 57637, 57641, 57649, 57653, 57667, 57679, 57689, 57697, 57709, 57713, 57719, 57727, 57731, 57737, 57751, 57773, 57781, 57787, 57791, 57793, 57803, 57809, 57829, 57839, 57847, 57853, 57859, 57881, 57899, 57901, 57917, 57923, 57943, 57947, 57973, 57977, 57991, 58013, 58027, 58031, 58043, 58049, 58057, 58061, 58067, 58073, 58099, 58109, 58111, 58129, 58147, 58151, 58153, 58169, 58171, 58189, 58193, 58199, 58207, 58211, 58217, 58229, 58231, 58237, 58243, 58271, 58309, 58313, 58321, 58337, 58363, 58367, 58369, 58379, 58391, 58393, 58403, 58411, 58417, 58427, 58439, 58441, 58451, 58453, 58477, 58481, 58511, 58537, 58543, 58549, 58567, 58573, 58579, 58601, 58603, 58613, 58631, 58657, 58661, 58679, 58687, 58693, 58699, 58711, 58727, 58733, 58741, 58757, 58763, 58771, 58787, 58789, 58831, 58889, 58897, 58901, 58907, 58909, 58913, 58921, 58937, 58943, 58963, 58967, 58979, 58991, 58997, 59009, 59011, 59021, 59023, 59029, 59051, 59053, 59063, 59069, 59077, 59083, 59093, 59107, 59113, 59119, 59123, 59141, 59149, 59159, 59167, 59183, 59197, 59207, 59209, 59219, 59221, 59233, 59239, 59243, 59263, 59273, 59281, 59333, 59341, 59351, 59357, 59359, 59369, 59377, 59387, 59393, 59399, 59407, 59417, 59419, 59441, 59443, 59447, 59453, 59467, 59471, 59473, 59497, 59509, 59513, 59539, 59557, 59561, 59567, 59581, 59611, 59617, 59621, 59627, 59629, 59651, 59659, 59663, 59669, 59671, 59693, 59699, 59707, 59723, 59729, 59743, 59747, 59753, 59771, 59779, 59791, 59797, 59809, 59833, 59863, 59879, 59887, 59921, 59929, 59951, 59957, 59971, 59981, 59999, 60013, 60017, 60029, 60037, 60041, 60077, 60083, 60089, 60091, 60101, 60103, 60107, 60127, 60133, 60139, 60149, 60161, 60167, 60169, 60209, 60217, 60223, 60251, 60257, 60259, 60271, 60289, 60293, 60317, 60331, 60337, 60343, 60353, 60373, 60383, 60397, 60413, 60427, 60443, 60449, 60457, 60493, 60497, 60509, 60521, 60527, 60539, 60589, 60601, 60607, 60611, 60617, 60623, 60631, 60637, 60647, 60649, 60659, 60661, 60679, 60689, 60703, 60719, 60727, 60733, 60737, 60757, 60761, 60763, 60773, 60779, 60793, 60811, 60821, 60859, 60869, 60887, 60889, 60899, 60901, 60913, 60917, 60919, 60923, 60937, 60943, 60953, 60961, 61001, 61007, 61027, 61031, 61043, 61051, 61057, 61091, 61099, 61121, 61129, 61141, 61151, 61153, 61169, 61211, 61223, 61231, 61253, 61261, 61283, 61291, 61297, 61331, 61333, 61339, 61343, 61357, 61363, 61379, 61381, 61403, 61409, 61417, 61441, 61463, 61469, 61471, 61483, 61487, 61493, 61507, 61511, 61519, 61543, 61547, 61553, 61559, 61561, 61583, 61603, 61609, 61613, 61627, 61631, 61637, 61643, 61651, 61657, 61667, 61673, 61681, 61687, 61703, 61717, 61723, 61729, 61751, 61757, 61781, 61813, 61819, 61837, 61843, 61861, 61871, 61879, 61909, 61927, 61933, 61949, 61961, 61967, 61979, 61981, 61987, 61991, 62003, 62011, 62017, 62039, 62047, 62053, 62057, 62071, 62081, 62099, 62119, 62129, 62131, 62137, 62141, 62143, 62171, 62189, 62191, 62201, 62207, 62213, 62219, 62233, 62273, 62297, 62299, 62303, 62311, 62323, 62327, 62347, 62351, 62383, 62401, 62417, 62423, 62459, 62467, 62473, 62477, 62483, 62497, 62501, 62507, 62533, 62539, 62549, 62563, 62581, 62591, 62597, 62603, 62617, 62627, 62633, 62639, 62653, 62659, 62683, 62687, 62701, 62723, 62731, 62743, 62753, 62761, 62773, 62791, 62801, 62819, 62827, 62851, 62861, 62869, 62873, 62897, 62903, 62921, 62927, 62929, 62939, 62969, 62971, 62981, 62983, 62987, 62989, 63029, 63031, 63059, 63067, 63073, 63079, 63097, 63103, 63113, 63127, 63131, 63149, 63179, 63197, 63199, 63211, 63241, 63247, 63277, 63281, 63299, 63311, 63313, 63317, 63331, 63337, 63347, 63353, 63361, 63367, 63377, 63389, 63391, 63397, 63409, 63419, 63421, 63439, 63443, 63463, 63467, 63473, 63487, 63493, 63499, 63521, 63527, 63533, 63541, 63559, 63577, 63587, 63589, 63599, 63601, 63607, 63611, 63617, 63629, 63647, 63649, 63659, 63667, 63671, 63689, 63691, 63697, 63703, 63709, 63719, 63727, 63737, 63743, 63761, 63773, 63781, 63793, 63799, 63803, 63809, 63823, 63839, 63841, 63853, 63857, 63863, 63901, 63907, 63913, 63929, 63949, 63977, 63997, 64007, 64013, 64019, 64033, 64037, 64063, 64067, 64081, 64091, 64109, 64123, 64151, 64153, 64157, 64171, 64187, 64189, 64217, 64223, 64231, 64237, 64271, 64279, 64283, 64301, 64303, 64319, 64327, 64333, 64373, 64381, 64399, 64403, 64433, 64439, 64451, 64453, 64483, 64489, 64499, 64513, 64553, 64567, 64577, 64579, 64591, 64601, 64609, 64613, 64621, 64627, 64633, 64661, 64663, 64667, 64679, 64693, 64709, 64717, 64747, 64763, 64781, 64783, 64793, 64811, 64817, 64849, 64853, 64871, 64877, 64879, 64891, 64901, 64919, 64921, 64927, 64937, 64951, 64969, 64997, 65003, 65011, 65027, 65029, 65033, 65053, 65063, 65071, 65089, 65099, 65101, 65111, 65119, 65123, 65129, 65141, 65147, 65167, 65171, 65173, 65179, 65183, 65203, 65213, 65239, 65257, 65267, 65269, 65287, 65293, 65309, 65323, 65327, 65353, 65357, 65371, 65381, 65393, 65407, 65413, 65419, 65423, 65437, 65447, 65449, 65479, 65497, 65519, 65521, 65537, 65539, 65543, 65551, 65557, 65563, 65579, 65581, 65587, 65599, 65609, 65617, 65629, 65633, 65647, 65651, 65657, 65677, 65687, 65699, 65701, 65707, 65713, 65717, 65719, 65729, 65731, 65761, 65777, 65789, 65809, 65827, 65831, 65837, 65839, 65843, 65851, 65867, 65881, 65899, 65921, 65927, 65929, 65951, 65957, 65963, 65981, 65983, 65993, 66029, 66037, 66041, 66047, 66067, 66071, 66083, 66089, 66103, 66107, 66109, 66137, 66161, 66169, 66173, 66179, 66191, 66221, 66239, 66271, 66293, 66301, 66337, 66343, 66347, 66359, 66361, 66373, 66377, 66383, 66403, 66413, 66431, 66449, 66457, 66463, 66467, 66491, 66499, 66509, 66523, 66529, 66533, 66541, 66553, 66569, 66571, 66587, 66593, 66601, 66617, 66629, 66643, 66653, 66683, 66697, 66701, 66713, 66721, 66733, 66739, 66749, 66751, 66763, 66791, 66797, 66809, 66821, 66841, 66851, 66853, 66863, 66877, 66883, 66889, 66919, 66923, 66931, 66943, 66947, 66949, 66959, 66973, 66977, 67003, 67021, 67033, 67043, 67049, 67057, 67061, 67073, 67079, 67103, 67121, 67129, 67139, 67141, 67153, 67157, 67169, 67181, 67187, 67189, 67211, 67213, 67217, 67219, 67231, 67247, 67261, 67271, 67273, 67289, 67307, 67339, 67343, 67349, 67369, 67391, 67399, 67409, 67411, 67421, 67427, 67429, 67433, 67447, 67453, 67477, 67481, 67489, 67493, 67499, 67511, 67523, 67531, 67537, 67547, 67559, 67567, 67577, 67579, 67589, 67601, 67607, 67619, 67631, 67651, 67679, 67699, 67709, 67723, 67733, 67741, 67751, 67757, 67759, 67763, 67777, 67783, 67789, 67801, 67807, 67819, 67829, 67843, 67853, 67867, 67883, 67891, 67901, 67927, 67931, 67933, 67939, 67943, 67957, 67961, 67967, 67979, 67987, 67993, 68023, 68041, 68053, 68059, 68071, 68087, 68099, 68111, 68113, 68141, 68147, 68161, 68171, 68207, 68209, 68213, 68219, 68227, 68239, 68261, 68279, 68281, 68311, 68329, 68351, 68371, 68389, 68399, 68437, 68443, 68447, 68449, 68473, 68477, 68483, 68489, 68491, 68501, 68507, 68521, 68531, 68539, 68543, 68567, 68581, 68597, 68611, 68633, 68639, 68659, 68669, 68683, 68687, 68699, 68711, 68713, 68729, 68737, 68743, 68749, 68767, 68771, 68777, 68791, 68813, 68819, 68821, 68863, 68879, 68881, 68891, 68897, 68899, 68903, 68909, 68917, 68927, 68947, 68963, 68993, 69001, 69011, 69019, 69029, 69031, 69061, 69067, 69073, 69109, 69119, 69127, 69143, 69149, 69151, 69163, 69191, 69193, 69197, 69203, 69221, 69233, 69239, 69247, 69257, 69259, 69263, 69313, 69317, 69337, 69341, 69371, 69379, 69383, 69389, 69401, 69403, 69427, 69431, 69439, 69457, 69463, 69467, 69473, 69481, 69491, 69493, 69497, 69499, 69539, 69557, 69593, 69623, 69653, 69661, 69677, 69691, 69697, 69709, 69737, 69739, 69761, 69763, 69767, 69779, 69809, 69821, 69827, 69829, 69833, 69847, 69857, 69859, 69877, 69899, 69911, 69929, 69931, 69941, 69959, 69991, 69997, 70001, 70003, 70009, 70019, 70039, 70051, 70061, 70067, 70079, 70099, 70111, 70117, 70121, 70123, 70139, 70141, 70157, 70163, 70177, 70181, 70183, 70199, 70201, 70207, 70223, 70229, 70237, 70241, 70249, 70271, 70289, 70297, 70309, 70313, 70321, 70327, 70351, 70373, 70379, 70381, 70393, 70423, 70429, 70439, 70451, 70457, 70459, 70481, 70487, 70489, 70501, 70507, 70529, 70537, 70549, 70571, 70573, 70583, 70589, 70607, 70619, 70621, 70627, 70639, 70657, 70663, 70667, 70687, 70709, 70717, 70729, 70753, 70769, 70783, 70793, 70823, 70841, 70843, 70849, 70853, 70867, 70877, 70879, 70891, 70901, 70913, 70919, 70921, 70937, 70949, 70951, 70957, 70969, 70979, 70981, 70991, 70997, 70999, 71011, 71023, 71039, 71059, 71069, 71081, 71089, 71119, 71129, 71143, 71147, 71153, 71161, 71167, 71171, 71191, 71209, 71233, 71237, 71249, 71257, 71261, 71263, 71287, 71293, 71317, 71327, 71329, 71333, 71339, 71341, 71347, 71353, 71359, 71363, 71387, 71389, 71399, 71411, 71413, 71419, 71429, 71437, 71443, 71453, 71471, 71473, 71479, 71483, 71503, 71527, 71537, 71549, 71551, 71563, 71569, 71593, 71597, 71633, 71647, 71663, 71671, 71693, 71699, 71707, 71711, 71713, 71719, 71741, 71761, 71777, 71789, 71807, 71809, 71821, 71837, 71843, 71849, 71861, 71867, 71879, 71881, 71887, 71899, 71909, 71917, 71933, 71941, 71947, 71963, 71971, 71983, 71987, 71993, 71999, 72019, 72031, 72043, 72047, 72053, 72073, 72077, 72089, 72091, 72101, 72103, 72109, 72139, 72161, 72167, 72169, 72173, 72211, 72221, 72223, 72227, 72229, 72251, 72253, 72269, 72271, 72277, 72287, 72307, 72313, 72337, 72341, 72353, 72367, 72379, 72383, 72421, 72431, 72461, 72467, 72469, 72481, 72493, 72497, 72503, 72533, 72547, 72551, 72559, 72577, 72613, 72617, 72623, 72643, 72647, 72649, 72661, 72671, 72673, 72679, 72689, 72701, 72707, 72719, 72727, 72733, 72739, 72763, 72767, 72797, 72817, 72823, 72859, 72869, 72871, 72883, 72889, 72893, 72901, 72907, 72911, 72923, 72931, 72937, 72949, 72953, 72959, 72973, 72977, 72997, 73009, 73013, 73019, 73037, 73039, 73043, 73061, 73063, 73079, 73091, 73121, 73127, 73133, 73141, 73181, 73189, 73237, 73243, 73259, 73277, 73291, 73303, 73309, 73327, 73331, 73351, 73361, 73363, 73369, 73379, 73387, 73417, 73421, 73433, 73453, 73459, 73471, 73477, 73483, 73517, 73523, 73529, 73547, 73553, 73561, 73571, 73583, 73589, 73597, 73607, 73609, 73613, 73637, 73643, 73651, 73673, 73679, 73681, 73693, 73699, 73709, 73721, 73727, 73751, 73757, 73771, 73783, 73819, 73823, 73847, 73849, 73859, 73867, 73877, 73883, 73897, 73907, 73939, 73943, 73951, 73961, 73973, 73999, 74017, 74021, 74027, 74047, 74051, 74071, 74077, 74093, 74099, 74101, 74131, 74143, 74149, 74159, 74161, 74167, 74177, 74189, 74197, 74201, 74203, 74209, 74219, 74231, 74257, 74279, 74287, 74293, 74297, 74311, 74317, 74323, 74353, 74357, 74363, 74377, 74381, 74383, 74411, 74413, 74419, 74441, 74449, 74453, 74471, 74489, 74507, 74509, 74521, 74527, 74531, 74551, 74561, 74567, 74573, 74587, 74597, 74609, 74611, 74623, 74653, 74687, 74699, 74707, 74713, 74717, 74719, 74729, 74731, 74747, 74759, 74761, 74771, 74779, 74797, 74821, 74827, 74831, 74843, 74857, 74861, 74869, 74873, 74887, 74891, 74897, 74903, 74923, 74929, 74933, 74941, 74959, 75011, 75013, 75017, 75029, 75037, 75041, 75079, 75083, 75109, 75133, 75149, 75161, 75167, 75169, 75181, 75193, 75209, 75211, 75217, 75223, 75227, 75239, 75253, 75269, 75277, 75289, 75307, 75323, 75329, 75337, 75347, 75353, 75367, 75377, 75389, 75391, 75401, 75403, 75407, 75431, 75437, 75479, 75503, 75511, 75521, 75527, 75533, 75539, 75541, 75553, 75557, 75571, 75577, 75583, 75611, 75617, 75619, 75629, 75641, 75653, 75659, 75679, 75683, 75689, 75703, 75707, 75709, 75721, 75731, 75743, 75767, 75773, 75781, 75787, 75793, 75797, 75821, 75833, 75853, 75869, 75883, 75913, 75931, 75937, 75941, 75967, 75979, 75983, 75989, 75991, 75997, 76001, 76003, 76031, 76039, 76079, 76081, 76091, 76099, 76103, 76123, 76129, 76147, 76157, 76159, 76163, 76207, 76213, 76231, 76243, 76249, 76253, 76259, 76261, 76283, 76289, 76303, 76333, 76343, 76367, 76369, 76379, 76387, 76403, 76421, 76423, 76441, 76463, 76471, 76481, 76487, 76493, 76507, 76511, 76519, 76537, 76541, 76543, 76561, 76579, 76597, 76603, 76607, 76631, 76649, 76651, 76667, 76673, 76679, 76697, 76717, 76733, 76753, 76757, 76771, 76777, 76781, 76801, 76819, 76829, 76831, 76837, 76847, 76871, 76873, 76883, 76907, 76913, 76919, 76943, 76949, 76961, 76963, 76991, 77003, 77017, 77023, 77029, 77041, 77047, 77069, 77081, 77093, 77101, 77137, 77141, 77153, 77167, 77171, 77191, 77201, 77213, 77237, 77239, 77243, 77249, 77261, 77263, 77267, 77269, 77279, 77291, 77317, 77323, 77339, 77347, 77351, 77359, 77369, 77377, 77383, 77417, 77419, 77431, 77447, 77471, 77477, 77479, 77489, 77491, 77509, 77513, 77521, 77527, 77543, 77549, 77551, 77557, 77563, 77569, 77573, 77587, 77591, 77611, 77617, 77621, 77641, 77647, 77659, 77681, 77687, 77689, 77699, 77711, 77713, 77719, 77723, 77731, 77743, 77747, 77761, 77773, 77783, 77797, 77801, 77813, 77839, 77849, 77863, 77867, 77893, 77899, 77929, 77933, 77951, 77969, 77977, 77983, 77999, 78007, 78017, 78031, 78041, 78049, 78059, 78079, 78101, 78121, 78137, 78139, 78157, 78163, 78167, 78173, 78179, 78191, 78193, 78203, 78229, 78233, 78241, 78259, 78277, 78283, 78301, 78307, 78311, 78317, 78341, 78347, 78367, 78401, 78427, 78437, 78439, 78467, 78479, 78487, 78497, 78509, 78511, 78517, 78539, 78541, 78553, 78569, 78571, 78577, 78583, 78593, 78607, 78623, 78643, 78649, 78653, 78691, 78697, 78707, 78713, 78721, 78737, 78779, 78781, 78787, 78791, 78797, 78803, 78809, 78823, 78839, 78853, 78857, 78877, 78887, 78889, 78893, 78901, 78919, 78929, 78941, 78977, 78979, 78989, 79031, 79039, 79043, 79063, 79087, 79103, 79111, 79133, 79139, 79147, 79151, 79153, 79159, 79181, 79187, 79193, 79201, 79229, 79231, 79241, 79259, 79273, 79279, 79283, 79301, 79309, 79319, 79333, 79337, 79349, 79357, 79367, 79379, 79393, 79397, 79399, 79411, 79423, 79427, 79433, 79451, 79481, 79493, 79531, 79537, 79549, 79559, 79561, 79579, 79589, 79601, 79609, 79613, 79621, 79627, 79631, 79633, 79657, 79669, 79687, 79691, 79693, 79697, 79699, 79757, 79769, 79777, 79801, 79811, 79813, 79817, 79823, 79829, 79841, 79843, 79847, 79861, 79867, 79873, 79889, 79901, 79903, 79907, 79939, 79943, 79967, 79973, 79979, 79987, 79997, 79999, 80021, 80039, 80051, 80071, 80077, 80107, 80111, 80141, 80147, 80149, 80153, 80167, 80173, 80177, 80191, 80207, 80209, 80221, 80231, 80233, 80239, 80251, 80263, 80273, 80279, 80287, 80309, 80317, 80329, 80341, 80347, 80363, 80369, 80387, 80407, 80429, 80447, 80449, 80471, 80473, 80489, 80491, 80513, 80527, 80537, 80557, 80567, 80599, 80603, 80611, 80621, 80627, 80629, 80651, 80657, 80669, 80671, 80677, 80681, 80683, 80687, 80701, 80713, 80737, 80747, 80749, 80761, 80777, 80779, 80783, 80789, 80803, 80809, 80819, 80831, 80833, 80849, 80863, 80897, 80909, 80911, 80917, 80923, 80929, 80933, 80953, 80963, 80989, 81001, 81013, 81017, 81019, 81023, 81031, 81041, 81043, 81047, 81049, 81071, 81077, 81083, 81097, 81101, 81119, 81131, 81157, 81163, 81173, 81181, 81197, 81199, 81203, 81223, 81233, 81239, 81281, 81283, 81293, 81299, 81307, 81331, 81343, 81349, 81353, 81359, 81371, 81373, 81401, 81409, 81421, 81439, 81457, 81463, 81509, 81517, 81527, 81533, 81547, 81551, 81553, 81559, 81563, 81569, 81611, 81619, 81629, 81637, 81647, 81649, 81667, 81671, 81677, 81689, 81701, 81703, 81707, 81727, 81737, 81749, 81761, 81769, 81773, 81799, 81817, 81839, 81847, 81853, 81869, 81883, 81899, 81901, 81919, 81929, 81931, 81937, 81943, 81953, 81967, 81971, 81973, 82003, 82007, 82009, 82013, 82021, 82031, 82037, 82039, 82051, 82067, 82073, 82129, 82139, 82141, 82153, 82163, 82171, 82183, 82189, 82193, 82207, 82217, 82219, 82223, 82231, 82237, 82241, 82261, 82267, 82279, 82301, 82307, 82339, 82349, 82351, 82361, 82373, 82387, 82393, 82421, 82457, 82463, 82469, 82471, 82483, 82487, 82493, 82499, 82507, 82529, 82531, 82549, 82559, 82561, 82567, 82571, 82591, 82601, 82609, 82613, 82619, 82633, 82651, 82657, 82699, 82721, 82723, 82727, 82729, 82757, 82759, 82763, 82781, 82787, 82793, 82799, 82811, 82813, 82837, 82847, 82883, 82889, 82891, 82903, 82913, 82939, 82963, 82981, 82997, 83003, 83009, 83023, 83047, 83059, 83063, 83071, 83077, 83089, 83093, 83101, 83117, 83137, 83177, 83203, 83207, 83219, 83221, 83227, 83231, 83233, 83243, 83257, 83267, 83269, 83273, 83299, 83311, 83339, 83341, 83357, 83383, 83389, 83399, 83401, 83407, 83417, 83423, 83431, 83437, 83443, 83449, 83459, 83471, 83477, 83497, 83537, 83557, 83561, 83563, 83579, 83591, 83597, 83609, 83617, 83621, 83639, 83641, 83653, 83663, 83689, 83701, 83717, 83719, 83737, 83761, 83773, 83777, 83791, 83813, 83833, 83843, 83857, 83869, 83873, 83891, 83903, 83911, 83921, 83933, 83939, 83969, 83983, 83987, 84011, 84017, 84047, 84053, 84059, 84061, 84067, 84089, 84121, 84127, 84131, 84137, 84143, 84163, 84179, 84181, 84191, 84199, 84211, 84221, 84223, 84229, 84239, 84247, 84263, 84299, 84307, 84313, 84317, 84319, 84347, 84349, 84377, 84389, 84391, 84401, 84407, 84421, 84431, 84437, 84443, 84449, 84457, 84463, 84467, 84481, 84499, 84503, 84509, 84521, 84523, 84533, 84551, 84559, 84589, 84629, 84631, 84649, 84653, 84659, 84673, 84691, 84697, 84701, 84713, 84719, 84731, 84737, 84751, 84761, 84787, 84793, 84809, 84811, 84827, 84857, 84859, 84869, 84871, 84913, 84919, 84947, 84961, 84967, 84977, 84979, 84991, 85009, 85021, 85027, 85037, 85049, 85061, 85081, 85087, 85091, 85093, 85103, 85109, 85121, 85133, 85147, 85159, 85193, 85199, 85201, 85213, 85223, 85229, 85237, 85243, 85247, 85259, 85297, 85303, 85313, 85331, 85333, 85361, 85363, 85369, 85381, 85411, 85427, 85429, 85439, 85447, 85451, 85453, 85469, 85487, 85513, 85517, 85523, 85531, 85549, 85571, 85577, 85597, 85601, 85607, 85619, 85621, 85627, 85639, 85643, 85661, 85667, 85669, 85691, 85703, 85711, 85717, 85733, 85751, 85781, 85793, 85817, 85819, 85829, 85831, 85837, 85843, 85847, 85853, 85889, 85903, 85909, 85931, 85933, 85991, 85999, 86011, 86017, 86027, 86029, 86069, 86077, 86083, 86111, 86113, 86117, 86131, 86137, 86143, 86161, 86171, 86179, 86183, 86197, 86201, 86209, 86239, 86243, 86249, 86257, 86263, 86269, 86287, 86291, 86293, 86297, 86311, 86323, 86341, 86351, 86353, 86357, 86369, 86371, 86381, 86389, 86399, 86413, 86423, 86441, 86453, 86461, 86467, 86477, 86491, 86501, 86509, 86531, 86533, 86539, 86561, 86573, 86579, 86587, 86599, 86627, 86629, 86677, 86689, 86693, 86711, 86719, 86729, 86743, 86753, 86767, 86771, 86783, 86813, 86837, 86843, 86851, 86857, 86861, 86869, 86923, 86927, 86929, 86939, 86951, 86959, 86969, 86981, 86993, 87011, 87013, 87037, 87041, 87049, 87071, 87083, 87103, 87107, 87119, 87121, 87133, 87149, 87151, 87179, 87181, 87187, 87211, 87221, 87223, 87251, 87253, 87257, 87277, 87281, 87293, 87299, 87313, 87317, 87323, 87337, 87359, 87383, 87403, 87407, 87421, 87427, 87433, 87443, 87473, 87481, 87491, 87509, 87511, 87517, 87523, 87539, 87541, 87547, 87553, 87557, 87559, 87583, 87587, 87589, 87613, 87623, 87629, 87631, 87641, 87643, 87649, 87671, 87679, 87683, 87691, 87697, 87701, 87719, 87721, 87739, 87743, 87751, 87767, 87793, 87797, 87803, 87811, 87833, 87853, 87869, 87877, 87881, 87887, 87911, 87917, 87931, 87943, 87959, 87961, 87973, 87977, 87991, 88001, 88003, 88007, 88019, 88037, 88069, 88079, 88093, 88117, 88129, 88169, 88177, 88211, 88223, 88237, 88241, 88259, 88261, 88289, 88301, 88321, 88327, 88337, 88339, 88379, 88397, 88411, 88423, 88427, 88463, 88469, 88471, 88493, 88499, 88513, 88523, 88547, 88589, 88591, 88607, 88609, 88643, 88651, 88657, 88661, 88663, 88667, 88681, 88721, 88729, 88741, 88747, 88771, 88789, 88793, 88799, 88801, 88807, 88811, 88813, 88817, 88819, 88843, 88853, 88861, 88867, 88873, 88883, 88897, 88903, 88919, 88937, 88951, 88969, 88993, 88997, 89003, 89009, 89017, 89021, 89041, 89051, 89057, 89069, 89071, 89083, 89087, 89101, 89107, 89113, 89119, 89123, 89137, 89153, 89189, 89203, 89209, 89213, 89227, 89231, 89237, 89261, 89269, 89273, 89293, 89303, 89317, 89329, 89363, 89371, 89381, 89387, 89393, 89399, 89413, 89417, 89431, 89443, 89449, 89459, 89477, 89491, 89501, 89513, 89519, 89521, 89527, 89533, 89561, 89563, 89567, 89591, 89597, 89599, 89603, 89611, 89627, 89633, 89653, 89657, 89659, 89669, 89671, 89681, 89689, 89753, 89759, 89767, 89779, 89783, 89797, 89809, 89819, 89821, 89833, 89839, 89849, 89867, 89891, 89897, 89899, 89909, 89917, 89923, 89939, 89959, 89963, 89977, 89983, 89989, 90001, 90007, 90011, 90017, 90019, 90023, 90031, 90053, 90059, 90067, 90071, 90073, 90089, 90107, 90121, 90127, 90149, 90163, 90173, 90187, 90191, 90197, 90199, 90203, 90217, 90227, 90239, 90247, 90263, 90271, 90281, 90289, 90313, 90353, 90359, 90371, 90373, 90379, 90397, 90401, 90403, 90407, 90437, 90439, 90469, 90473, 90481, 90499, 90511, 90523, 90527, 90529, 90533, 90547, 90583, 90599, 90617, 90619, 90631, 90641, 90647, 90659, 90677, 90679, 90697, 90703, 90709, 90731, 90749, 90787, 90793, 90803, 90821, 90823, 90833, 90841, 90847, 90863, 90887, 90901, 90907, 90911, 90917, 90931, 90947, 90971, 90977, 90989, 90997, 91009, 91019, 91033, 91079, 91081, 91097, 91099, 91121, 91127, 91129, 91139, 91141, 91151, 91153, 91159, 91163, 91183, 91193, 91199, 91229, 91237, 91243, 91249, 91253, 91283, 91291, 91297, 91303, 91309, 91331, 91367, 91369, 91373, 91381, 91387, 91393, 91397, 91411, 91423, 91433, 91453, 91457, 91459, 91463, 91493, 91499, 91513, 91529, 91541, 91571, 91573, 91577, 91583, 91591, 91621, 91631, 91639, 91673, 91691, 91703, 91711, 91733, 91753, 91757, 91771, 91781, 91801, 91807, 91811, 91813, 91823, 91837, 91841, 91867, 91873, 91909, 91921, 91939, 91943, 91951, 91957, 91961, 91967, 91969, 91997, 92003, 92009, 92033, 92041, 92051, 92077, 92083, 92107, 92111, 92119, 92143, 92153, 92173, 92177, 92179, 92189, 92203, 92219, 92221, 92227, 92233, 92237, 92243, 92251, 92269, 92297, 92311, 92317, 92333, 92347, 92353, 92357, 92363, 92369, 92377, 92381, 92383, 92387, 92399, 92401, 92413, 92419, 92431, 92459, 92461, 92467, 92479, 92489, 92503, 92507, 92551, 92557, 92567, 92569, 92581, 92593, 92623, 92627, 92639, 92641, 92647, 92657, 92669, 92671, 92681, 92683, 92693, 92699, 92707, 92717, 92723, 92737, 92753, 92761, 92767, 92779, 92789, 92791, 92801, 92809, 92821, 92831, 92849, 92857, 92861, 92863, 92867, 92893, 92899, 92921, 92927, 92941, 92951, 92957, 92959, 92987, 92993, 93001, 93047, 93053, 93059, 93077, 93083, 93089, 93097, 93103, 93113, 93131, 93133, 93139, 93151, 93169, 93179, 93187, 93199, 93229, 93239, 93241, 93251, 93253, 93257, 93263, 93281, 93283, 93287, 93307, 93319, 93323, 93329, 93337, 93371, 93377, 93383, 93407, 93419, 93427, 93463, 93479, 93481, 93487, 93491, 93493, 93497, 93503, 93523, 93529, 93553, 93557, 93559, 93563, 93581, 93601, 93607, 93629, 93637, 93683, 93701, 93703, 93719, 93739, 93761, 93763, 93787, 93809, 93811, 93827, 93851, 93871, 93887, 93889, 93893, 93901, 93911, 93913, 93923, 93937, 93941, 93949, 93967, 93971, 93979, 93983, 93997, 94007, 94009, 94033, 94049, 94057, 94063, 94079, 94099, 94109, 94111, 94117, 94121, 94151, 94153, 94169, 94201, 94207, 94219, 94229, 94253, 94261, 94273, 94291, 94307, 94309, 94321, 94327, 94331, 94343, 94349, 94351, 94379, 94397, 94399, 94421, 94427, 94433, 94439, 94441, 94447, 94463, 94477, 94483, 94513, 94529, 94531, 94541, 94543, 94547, 94559, 94561, 94573, 94583, 94597, 94603, 94613, 94621, 94649, 94651, 94687, 94693, 94709, 94723, 94727, 94747, 94771, 94777, 94781, 94789, 94793, 94811, 94819, 94823, 94837, 94841, 94847, 94849, 94873, 94889, 94903, 94907, 94933, 94949, 94951, 94961, 94993, 94999, 95003, 95009, 95021, 95027, 95063, 95071, 95083, 95087, 95089, 95093, 95101, 95107, 95111, 95131, 95143, 95153, 95177, 95189, 95191, 95203, 95213, 95219, 95231, 95233, 95239, 95257, 95261, 95267, 95273, 95279, 95287, 95311, 95317, 95327, 95339, 95369, 95383, 95393, 95401, 95413, 95419, 95429, 95441, 95443, 95461, 95467, 95471, 95479, 95483, 95507, 95527, 95531, 95539, 95549, 95561, 95569, 95581, 95597, 95603, 95617, 95621, 95629, 95633, 95651, 95701, 95707, 95713, 95717, 95723, 95731, 95737, 95747, 95773, 95783, 95789, 95791, 95801, 95803, 95813, 95819, 95857, 95869, 95873, 95881, 95891, 95911, 95917, 95923, 95929, 95947, 95957, 95959, 95971, 95987, 95989, 96001, 96013, 96017, 96043, 96053, 96059, 96079, 96097, 96137, 96149, 96157, 96167, 96179, 96181, 96199, 96211, 96221, 96223, 96233, 96259, 96263, 96269, 96281, 96289, 96293, 96323, 96329, 96331, 96337, 96353, 96377, 96401, 96419, 96431, 96443, 96451, 96457, 96461, 96469, 96479, 96487, 96493, 96497, 96517, 96527, 96553, 96557, 96581, 96587, 96589, 96601, 96643, 96661, 96667, 96671, 96697, 96703, 96731, 96737, 96739, 96749, 96757, 96763, 96769, 96779, 96787, 96797, 96799, 96821, 96823, 96827, 96847, 96851, 96857, 96893, 96907, 96911, 96931, 96953, 96959, 96973, 96979, 96989, 96997, 97001, 97003, 97007, 97021, 97039, 97073, 97081, 97103, 97117, 97127, 97151, 97157, 97159, 97169, 97171, 97177, 97187, 97213, 97231, 97241, 97259, 97283, 97301, 97303, 97327, 97367, 97369, 97373, 97379, 97381, 97387, 97397, 97423, 97429, 97441, 97453, 97459, 97463, 97499, 97501, 97511, 97523, 97547, 97549, 97553, 97561, 97571, 97577, 97579, 97583, 97607, 97609, 97613, 97649, 97651, 97673, 97687, 97711, 97729, 97771, 97777, 97787, 97789, 97813, 97829, 97841, 97843, 97847, 97849, 97859, 97861, 97871, 97879, 97883, 97919, 97927, 97931, 97943, 97961, 97967, 97973, 97987, 98009, 98011, 98017, 98041, 98047, 98057, 98081, 98101, 98123, 98129, 98143, 98179, 98207, 98213, 98221, 98227, 98251, 98257, 98269, 98297, 98299, 98317, 98321, 98323, 98327, 98347, 98369, 98377, 98387, 98389, 98407, 98411, 98419, 98429, 98443, 98453, 98459, 98467, 98473, 98479, 98491, 98507, 98519, 98533, 98543, 98561, 98563, 98573, 98597, 98621, 98627, 98639, 98641, 98663, 98669, 98689, 98711, 98713, 98717, 98729, 98731, 98737, 98773, 98779, 98801, 98807, 98809, 98837, 98849, 98867, 98869, 98873, 98887, 98893, 98897, 98899, 98909, 98911, 98927, 98929, 98939, 98947, 98953, 98963, 98981, 98993, 98999, 99013, 99017, 99023, 99041, 99053, 99079, 99083, 99089, 99103, 99109, 99119, 99131, 99133, 99137, 99139, 99149, 99173, 99181, 99191, 99223, 99233, 99241, 99251, 99257, 99259, 99277, 99289, 99317, 99347, 99349, 99367, 99371, 99377, 99391, 99397, 99401, 99409, 99431, 99439, 99469, 99487, 99497, 99523, 99527, 99529, 99551, 99559, 99563, 99571, 99577, 99581, 99607, 99611, 99623, 99643, 99661, 99667, 99679, 99689, 99707, 99709, 99713, 99719, 99721, 99733, 99761, 99767, 99787, 99793, 99809, 99817, 99823, 99829, 99833, 99839, 99859, 99871, 99877, 99881, 99901, 99907, 99923, 99929, 99961, 99971, 99989, 99991]
X = [0] * (10 ** 5 + 1)
inv = [0] * (10 ** 5 + 1)
for p in P:
	X[p] = 1
Ps = P[:65]
for i in range(len(P)):
	inv[P[i]] = i + 1
N = int(input())
ANS = []
for n in range(2, N + 1):
	if X[n]:
		ANS.append(inv[n])
	else:
		for p in Ps:
			if n % p == 0:
				ANS.append(inv[p])
				break
print(*ANS)


import math
n = int(input())
a = [1] * (n - 1)
num = 2
prime = []
for i in range(3, n + 1, 2):
	if all((i % j != 0 for j in range(3, int(math.sqrt(i)) + 1, 2))):
		prime.append(i)
for i in prime:
	j = i
	while j - 2 < n - 1:
		a[j - 2] = num
		j += i
	num += 1
print(' '.join([str(i) for i in a]))


n = int(input())
arr = [0] * (n - 1)
count = 1
i = 2
while i < n + 1:
	if arr[i - 2] == 0:
		a = i - 2
		while a < n - 1:
			if arr[a] == 0:
				arr[a] = count
			a += i
		count += 1
	i += 1
ans = ''
for a in arr:
	ans += str(a) + ' '
print(ans)


def solve(n):
	a = [0 for _ in range(100001)]
	cnt = 1
	for i in range(2, n + 1):
		if a[i] == 0:
			for j in range(i, n + 1, i):
				if a[j] == 0:
					a[j] = cnt
			cnt += 1
	res = []
	for i in range(1, n):
		res.append(str(a[i + 1]))
	return ' '.join(res)
n = int(input())
print(solve(n))


n = int(input())
res = [0] * (10 ** 6 + 1)
flag = [False] * (10 ** 6 + 1)
count = 0
for i in range(2, n + 1):
	if not flag[i]:
		count += 1
		res[i] = count
	j = i * 2
	while j <= n + 1:
		res[j] = res[i]
		flag[j] = True
		j += i
	i += 1
aux = []
for i in range(2, n + 1):
	aux.append(res[i])
print(*aux)


def is_comp(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return i
		i += 1
	return False
n = int(input())
ans = []
j = 1
for i in range(2, n + 1):
	if not is_comp(i):
		ans.append(j)
		j += 1
	else:
		ans.append(ans[is_comp(i) - 2])
print(*ans)


from math import sqrt

def is_prime(n):
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def boo(n):
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			return i
hash = {}
n = int(input())
ans = [0] * (n - 1)
for i in range(0, n - 1, 2):
	ans[i] = 1
count = 2
la = []
for i in range(1, n - 1, 2):
	if is_prime(i + 2) == True:
		ans[i] = count
		hash[i + 2] = count
		count += 1
		la.append(i + 2)
	else:
		j = boo(i + 2)
		ans[i] = hash[j]
print(*ans)


n = int(input())

def pr(x):
	for i in range(2, x):
		if x % i == 0:
			return False
	else:
		return True
z = 1
l = [0] * (n - 1)
for i in range(2, n + 1):
	if l[i - 2] > 0:
		continue
	else:
		f = 1
		while i * f <= n:
			if l[i * f - 2] == 0:
				l[i * f - 2] = z
			f += 1
		z += 1
print(*l)


from math import *
n = int(input())
sieve = [0] * (n + 1)
k = 1
for i in range(2, n + 1):
	if not sieve[i]:
		sieve[i] = k
		j = 0
		while i * (i + j) <= n:
			if not sieve[i * (i + j)]:
				sieve[i * (i + j)] = k
			j += 1
		k += 1
	else:
		continue
sieve.pop(0)
sieve.pop(0)
print(*sieve)


import math
primes = [2]
n = int(input())
curr_num = 1
res = [1]
for i in range(3, n + 1):
	is_prime = True
	limit = math.ceil(math.sqrt(i))
	for p in primes:
		if i % p == 0:
			res.append(res[p - 2])
			is_prime = False
			break
		if p > limit:
			break
	if is_prime:
		curr_num += 1
		res.append(curr_num)
		primes.append(i)
print(' '.join(map(str, res)))


n = int(input())
arr = [None for i in range(n + 1)]
num = 1
for i in range(2, n + 1):
	if arr[i] == None:
		arr[i] = num
		j = i
		while j + i <= n:
			j += i
			arr[j] = num
		num += 1
for i in range(2, n + 1):
	print(arr[i], end=' ')


n = int(input())
arr = list(range(0, n + 1))
crr = [0] * (n + 1)
brr = []
for i in range(2, len(arr)):
	if arr[i] != 0:
		brr.append(arr[i])
		crr[i] = len(brr)
		for j in range(2 * i, n + 1, i):
			crr[j] = len(brr)
			arr[j] = 0
print(*crr[2:])


import math
n = int(input())
b = [0] * (n + 1)
j = 0
for i in range(2, n + 1):
	if b[i] == 0:
		j += 1
		for k in range(1, n // i + 1):
			b[k * i] = j
for i in range(2, n + 1):
	print(b[i], end=' ')


n = int(input())
aux = [0] * (n + 1)
x = 1
for i in range(2, n + 1):
	if aux[i] == 0:
		aux[i] = x
		for j in range(i * i, n + 1, i):
			aux[j] = x
		x += 1
print(*aux[2:n + 1])


def prime(n):
	a = [0] * (n + 1)
	p = [0] * (n + 1)
	k = 0
	for i in range(2, n + 1):
		if a[i] == 0:
			k += 1
			p[i] = k
			a[i] = 1
			for j in range(i, n + 1, i):
				if a[j] == 0:
					p[j] = k
					a[j] = 1
	return p
n = int(input())
print(*prime(n)[2:])


a = int(input())
z = [0] * (a + 1)
k = 2
for j in range(2, a + 1, 2):
	z[j] = 1
for i in range(3, a + 1, 2):
	if z[i] == 0:
		for j in range(i, a + 1, i):
			z[j] = k
		k += 1
z.pop(0)
z.pop(0)
print(*z)


import os, sys, shutil, glob, re
import time, calendar
from datetime import datetime, timezone
import hashlib, zipfile, zlib
from math import *
from operator import itemgetter
from functools import wraps, cmp_to_key, reduce, lru_cache
from itertools import count, combinations, permutations
from collections import namedtuple, defaultdict, Counter, deque
from queue import Queue
from bisect import bisect_left, bisect_right

class CustomException(Exception):
	pass
if os.getenv('SJDEAK'):
	debug = print
else:
	debug = lambda *args, **kwargs: None

def sieve(n):
	isp = [1] * (n + 1)
	isp[0] = isp[1] = 0
	pCnt = 0
	for i in range(2, n + 1):
		if isp[i]:
			pCnt += 1
			for j in range(i * i, i * (n // i + 1), i):
				isp[j] = pCnt
N = int(input())
ans = []
primeCnt = 0
isp = [(True, 0)] * (N + 1)
isp[0] = isp[1] = (False, 0)
pCnt = 0
for i in range(2, N + 1):
	if isp[i][0]:
		pCnt += 1
		isp[i] = (True, pCnt)
		for j in range(i * i, i * (N // i + 1), i):
			isp[j] = (False, pCnt)
print(*map(itemgetter(1), isp[2:]))


import sys, math, queue, bisect
MOD = 10 ** 9 + 7
sys.setrecursionlimit(1000000)
n = int(input())
a = [True for i in range(n + 1)]
c = 1
ans = [-1 for i in range(n + 1)]
for i in range(2, n + 1):
	if a[i]:
		ans[i] = c
		for j in range(i + i, n + 1, i):
			a[j] = False
			ans[j] = c
		c += 1
print(*ans[2:])


from math import *

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
n = int(input())
temp = SieveOfEratosthenes(n)
val = 1
arr1 = []
for i in range(2, n + 1):
	if temp[i] == True:
		arr1.append(i)
ansarr = [0] * (n + 1)
for i in range(len(arr1)):
	j = arr1[i]
	while j <= n:
		ansarr[j] = val
		j += arr1[i]
	val += 1
print(*ansarr[2:])


import math as mt
MAXN = 100001
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret
sieve()
n = int(input())
seq = []
color = [0] * (n + 1)
i = 1
for e in range(2, n + 1):
	seq.append(e)
for c in range(len(seq)):
	num = seq[c]
	mp = getFactorization(num)[0]
	if color[mp] == 0:
		color[mp] = i
		i += 1
	seq[c] = color[mp]
for w in range(len(seq)):
	print(seq[w], end=' ')


def is_prime(i):
	return True

def get_next_prime():
	i = 2
	while True:
		if is_prime(i):
			yield i
			i += 1

def run():
	n = eval(input())
	nums = [0] * (n - 1)
	g = get_next_prime()
	current = next(g)
	last = current
	for i in range(2, n + 1):
		j = i
		enter = False
		while j < n + 1:
			if nums[j - 2] == 0:
				enter = True
				last = current
				nums[j - 2] = current
			j += i
		if enter:
			current = next(g)
	for i in range(n - 1):
		if nums[i] == last:
			nums[i] = 1
	print(' '.join(list(map(str, nums))))
run()


from sys import stdin, setrecursionlimit, stdout
setrecursionlimit(100)
from collections import deque
from math import sqrt, floor, ceil, log, log2, log10, pi, gcd, sin, cos, asin
from heapq import heapify, heappop, heappush, heapreplace, heappushpop
from bisect import bisect_right, bisect_left

def ii():
	return int(stdin.readline())

def fi():
	return float(stdin.readline())

def mi():
	return map(int, stdin.readline().split())

def fmi():
	return map(float, stdin.readline().split())

def li():
	return list(mi())

def si():
	return stdin.readline().rstrip()

def lsi():
	return list(si())
mod = 1000000007
res = ['NO', 'YES']

def sieve(x):
	a = [1] * (x + 1)
	val = 1
	for i in range(3, x + 1, 2):
		if a[i] == 1:
			val += 1
			for j in range(i, x + 1, i):
				a[j] = val
	return a[2:]
test = test_case = 1
while test <= test_case:
	test += 1
	print(*sieve(ii()))


from math import sqrt
n = int(input())

def is_prime(x):
	for i in range(2, int(sqrt(x)) + 1):
		if x % i == 0:
			return
	return True
a = [0 for _ in range(n)]
primes = [x for x in range(2, n + 1) if is_prime(x)]
c = 1
for p in primes:
	for i in range(1, n // p + 1):
		a[i * p - 1] = c
	c += 1
print(*[x for x in a[1:]])


n = int(input())
a = [0 for i in range(n + 1)]
i = 2
sc = 1
while i * i <= n:
	if a[i] == 0:
		a[i] = sc
		j = i * i
		while j <= n:
			a[j] = sc
			j += i
		sc += 1
	i += 1
for i in range(2, n + 1):
	if a[i] == 0:
		a[i] = sc
		sc += 1
print(' '.join(map(str, a[2:])))


I = lambda : map(int, input().split())
n = int(input())
visit = [0 for i in range(n + 1)]
answer = [0 for i in range(n + 1)]
t = 0
for i in range(2, n + 1):
	if visit[i] == 0:
		t += 1
		visit[i] = 1
		answer[i] = t
		for j in range(i, n + 1, i):
			visit[j] = 1
			answer[j] = t
print(*answer[2:n + 1])


n = int(input())
n += 1
cur = 1
sieve = [1] * n
for i in range(3, n, 2):
	if sieve[i] == 1:
		cur += 1
		sieve[i] = cur
		sieve[i * i::2 * i] = [cur] * ((n - i * i - 1) // (2 * i) + 1)
print(*sieve[2:])


n = int(input())
is_prime = [-1] * (n - 1)
u = 1
for d in range(2, n + 1):
	if is_prime[d - 2] == -1:
		is_prime[d - 2] = u
		u += 1
	for comp in range(2 * d, n + 1, d):
		is_prime[comp - 2] = is_prime[d - 2]
print(*is_prime)


import math
n = int(input())
arr = [0] * (n + 1)
coPrimeSetter = 1
for i in range(2, n + 1):
	find = False
	for j in range(2, int(round(math.sqrt(i), 0)) + 1):
		if i % j == 0:
			find = True
			break
	if not find:
		arr[i] = coPrimeSetter
		coPrimeSetter += 1
	else:
		arr[i] = arr[j]
ans = ''
space = False
for i in range(2, n + 1):
	if space:
		ans += ' '
	space = True
	ans += str(arr[i])
print(ans)


n = int(input())
if n == 2:
	print('1')
	exit()
a = [0] * (n - 1)
k = 0
for i in range(2, n + 1):
	if a[i - 2] == 0:
		k += 1
		a[i - 2] = k
		j = i - 2
		while j <= n - 2:
			a[j] = a[i - 2]
			j += i
print(' '.join(list(map(str, a))))


from sys import stdin, stdout
import math, sys
from itertools import permutations, combinations
from collections import defaultdict, deque, OrderedDict
from os import path
import bisect as bi
import heapq

def yes():
	print('YES')

def no():
	print('NO')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

	def I():
		return int(input())

	def In():
		return map(int, input().split())
else:

	def I():
		return int(stdin.readline())

	def In():
		return map(int, stdin.readline().split())

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	ans = {}
	for p in range(n + 1):
		if prime[p]:
			ans[p] = 1
	return ans

def find_gt(a, x):
	i = bi.bisect_right(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		d = SieveOfEratosthenes(100000)
		n = I()
		dp = [10000000.0] * n
		j = 0
		for x in range(2, n + 1):
			if d.get(x, -1) != -1:
				j += 1
				for i in range(x, n + 1, x):
					dp[i - 1] = min(dp[i - 1], j)
		dp.pop(0)
		print(*dp)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


n = int(input())
a = [-1] * (n + 1)
ele = 1
for i in range(2, n + 1):
	if a[i] == -1:
		j = i
		while j <= n:
			a[j] = ele
			j += i
		ele += 1
for i in range(2, n + 1):
	print(a[i], end=' ')


n = int(input())
arr = [0 for i in range(n + 1)]
curr = 0
for i in range(2, len(arr)):
	if not arr[i]:
		curr += 1
		arr[i] = curr
		for j in range(i, len(arr), i):
			arr[j] = curr
	print(arr[i], end=' ')


n = int(input())
ans = [0] * (n + 1)
count = 1
for i in range(2, n + 1):
	if ans[i] == 0:
		for j in range(i, n + 1, i):
			ans[j] = count
		count += 1
print(' '.join(map(str, ans[2:])))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	n = N()
	res = [0] * (n + 1)
	now = 1
	for i in range(2, n + 1):
		if res[i] != 0:
			continue
		tag = i
		while tag <= n:
			if res[tag] == 0:
				res[tag] = now
			tag += i
		now += 1
	print(*res[2:])
main()


from sys import stdin
import heapq
import collections

def get_spf():
	mx = 10 ** 5
	spf = [x for x in range(mx + 1)]
	for i in range(2, mx + 1):
		if spf[i] == i:
			for j in range(i * i, mx + 1, i):
				if spf[j] == j:
					spf[j] = i
	prime = dict()
	for i in range(2, mx + 1):
		if spf[i] == i:
			prime[i] = True
	return (spf, prime)
n = int(stdin.readline().strip())
(spf, prime) = get_spf()
arr = [1] * (n + 1)
max_prime = 2
arr[2] = 1
for i in range(3, n + 1, 2):
	if i == spf[i]:
		arr[i] = max_prime
		max_prime += 1
	else:
		arr[i] = arr[spf[i]]
print(*arr[2:])


n = int(input())
seive = [0 for i in range(n + 1)]
seive[0] = 0
seive[1] = 1
counter = 1
for i in range(2, n + 1):
	if seive[i] == 0:
		seive[i] = counter
		for j in range(i * i, n + 1, i):
			seive[j] = counter
		counter += 1
for i in range(2, n + 1):
	print(seive[i], end=' ')


def sieve(n):
	res = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			res.append(p)
	return res
n = int(input())
primes = sieve(n + 1)
primes.reverse()
r = [0] * (n + 1)
color = 1
while len(primes) > 0:
	a = primes.pop()
	t = a
	while a < n + 1:
		if r[a] == 0:
			r[a] = color
		a += t
	color += 1
[print(i, end=' ') for i in r[2:]]


n = int(input()) + 1
res = ['0'] * n
count = 1
for i in range(2, n):
	if res[i] != '0':
		continue
	for j in range(i, n, i):
		res[j] = str(count)
	count += 1
print(' '.join(res[2:]))


def main():
	buf = input()
	n = int(buf)
	prime_map = dict()
	a = []
	for i in range(2, n + 1):
		first_prime = first_prime_factor(i)
		if first_prime not in prime_map:
			prime_map[first_prime] = len(prime_map) + 1
		a.append(prime_map[first_prime])
	print(' '.join(list(map(str, a))))

def first_prime_factor(x):
	n = x
	i = 2
	while i * i <= n:
		if n % i == 0:
			return i
		i += 1
	return x
main()


import math
val_dict = dict()

def smallest(n):
	while n % 2 == 0:
		return 2
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			return i
			n = n / i
	if n > 2:
		return n
assign = 1
n = int(input())
for i in range(2, n + 1):
	x = smallest(i)
	if x == i:
		val_dict[i] = assign
		assign += 1
	else:
		val_dict[i] = val_dict[x]
for (k, v) in val_dict.items():
	print(v, end=' ')


n = int(input())
z = 1
arr = [0 for _ in range(n + 1)]
for i in range(2, n + 1):
	if arr[i] == 0:
		arr[i] = z
		j = i * i
		while j < n + 1:
			arr[j] = z
			j += i
		z += 1
for k in range(2, n + 1):
	print(arr[k], end=' ')


n = int(input())

def get_min_divisor(x):
	for i in range(2, int(pow(x, 1 / 2) + 1)):
		if x % i == 0:
			return i
	return 1
out = (n + 1) * [-1]
curr = 1
out[2] = curr
for i in range(3, n + 1):
	min_div = get_min_divisor(i)
	if out[min_div] == -1:
		curr += 1
		out[i] = curr
	else:
		out[i] = out[min_div]
print(' '.join([str(x) for x in out[2:]]))


from math import sqrt
n = int(input())
a = [0 for i in range(n + 1)]
cnt = 1
a[2] = 1
for i in range(2, n + 1):
	for j in range(2, int(sqrt(i)) + 1):
		if i % j == 0:
			a[i] = a[j]
			break
	if a[i] == 0:
		cnt += 1
		a[i] = cnt
for i in a[2:]:
	print(i, end=' ')


n = int(input())
prime = [True for i in range(n + 1)]
l = [-1 for i in range(n + 1)]
p = 2
c = 0
while p * p <= n:
	if prime[p] == True:
		c += 1
		l[p] = c
		for i in range(p * p, n + 1, p):
			prime[i] = False
			l[i] = c
	p += 1
for i in range(2, n + 1):
	if l[i] == -1:
		c += 1
		print(c, end=' ')
	else:
		print(l[i], end=' ')


import math

def get_ans(n):
	ans = [1]
	max_num = 1
	for i in range(3, n + 1):
		cur_num = max_num + 1
		for j in range(2, int(math.sqrt(i)) + 1):
			if i % j == 0:
				cur_num = min(cur_num, ans[j - 2])
		max_num = max(max_num, cur_num)
		ans.append(cur_num)
	return ans

def main():
	n = int(input())
	print(' '.join((str(i) for i in get_ans(n))))
main()


from sys import stdin

def input():
	return stdin.readline().strip()
n = int(input())
l = [-1] * (n + 1)
is_prime = [True] * (n + 1)
count = 0
for i in range(2, n + 1):
	if is_prime[i]:
		count += 1
		for j in range(i, n + 1, i):
			l[j] = count
			is_prime[j] = False
print(*l[2:])


n = int(input())
list = ['0'] * 1000000
count = 1
for i in range(2, n + 1, 1):
	if list[i] == '0':
		for j in range(i, n + 1, i):
			if list[j] == '0':
				list[j] = str(count)
		count += 1
print(' '.join(list[2:n + 1]))


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return [i for i in range(2, len(prime)) if prime[i]]
n = int(input())
arr = SieveOfEratosthenes(n)
ans = [0] * n
c = 0
for i in arr:
	c += 1
	for j in range(i - 1, len(ans), i):
		ans[j] = c
print(*ans[1:])


n = int(input())
mx = n - n // 2
ans = [0 for i in range(n - 1)]
k = 1
for i in range(2, n + 1, 1):
	if ans[i - 2] != 0:
		continue
	ans[i - 2] = k
	x = 2
	while i * x <= n:
		if ans[i * x - 2] == 0:
			ans[i * x - 2] = k
		x += 1
	k += 1
print(' '.join([str(i) for i in ans]))


import sys
input = sys.stdin.readline
from collections import defaultdict
d = defaultdict(int)
i = 1
n = int(input())
primes = [2, 3, 5, 7]
if n > 10:
	for j in range(11, n + 1):
		for x in primes:
			if j % x == 0:
				break
		else:
			primes.append(j)
for x in primes:
	d[x] = i
	i += 1
l = []
for j in range(2, n + 1):
	for x in primes:
		if j % x == 0:
			l.append(d[x])
			break
print(*l)


n = int(input())
a = [0 for j in range(n + 1)]
c = 1
for j in range(2, n + 1):
	if a[j] != 0:
		continue
	else:
		k = j
		while k < n + 1:
			a[k] = c
			k = k + j
		c = c + 1
print(' '.join(map(str, a[2:])))


def main():
	n = int(input())
	nums = [i for i in range(2, n + 1)]
	a = [0 for i in range(2, n + 1)]
	cur = 1
	for i in range(n - 1):
		if a[i] == 0:
			a[i] = cur
			index = i
			while index < n - 1:
				a[index] = cur
				index += nums[i]
			cur += 1
	print(' '.join(map(str, a)))
main()


n = int(input())
p = [0] * (n + 5)
ans = [0] * (n + 5)
t = 0
for i in range(2, n + 5):
	if p[i] == 0:
		j = i + i
		t += 1
		ans[i] = t
		while j < n + 5:
			p[j] = 1
			ans[j] = t
			j += i
print(*ans[2:n + 1])


n = int(input())
c = [0] * (n + 1)
d = 0
for i in range(2, n + 1):
	if not c[i]:
		d += 1
		for j in range(i, n + 1, i):
			c[j] = d
print(' '.join(map(str, c[2:])))


n = int(input())
markings = [0 for i in range(n)]
c = 1
for i in range(1, n):
	if markings[i] == 0:
		for j in range(i, n, i + 1):
			markings[j] = c
		c += 1
for i in range(1, n):
	print(markings[i], end=' ')
print('')


def isPrime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
n = int(input())
b = []
c = []
s = 0
for i in range(2, n + 1):
	if isPrime(i):
		b.append([i, s + 1])
		s = s + 1
		c.append(s)
	else:
		for j in range(s):
			if i % b[j][0] == 0:
				c.append(b[j][1])
				break
print(*c)


import sys
input = sys.stdin.readline

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0, hi=None):
	if hi == None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]
spf_sieve()

def factoriazation(x):
	ret = {}
	while x != 1:
		ret[spf[x]] = ret.get(spf[x], 0) + 1
		x = x // spf[x]
	return ret

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

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
n = int(input())
ans = []
start = 1
this = {}
for i in range(2, n + 1):
	if spf[i] == i:
		this[i] = start
		ans.append(start)
		start += 1
	else:
		ans.append(this[spf[i]])
		this[i] = ans[-1]
print(*ans)


n = int(input())
k = 1
dp = []
for i in range(1, n + 5):
	dp.append(0)
for i in range(2, n + 1, 2):
	dp[i] = k
for i in range(3, n + 1, 2):
	if dp[i] == 0:
		k += 1
		for j in range(i, n + 1, i):
			dp[j] = k
for i in range(2, n + 1):
	print(dp[i])


import math
import bisect
import heapq
from collections import defaultdict

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, x, y) = egcd(b % a, a)
		return (g, y - b // a * x, x)

def mulinv(b, n):
	(g, x, _) = egcd(b, n)
	if g == 1:
		return x % n

def isprime(n):
	for d in range(2, int(math.sqrt(n)) + 1):
		if n % d == 0:
			return False
	return True

def argsort(ls):
	return sorted(range(len(ls)), key=ls.__getitem__)

def f(p=0):
	if p == 1:
		return map(int, input().split())
	elif p == 2:
		return list(map(int, input().split()))
	elif p == 3:
		return list(input())
	else:
		return int(input())

class DisjointSet:
	_disjoint_set = list()

	def __init__(self, init_arr):
		self._disjoint_set = []
		if init_arr:
			for item in list(set(init_arr)):
				self._disjoint_set.append([item])

	def _find_index(self, elem):
		for item in self._disjoint_set:
			if elem in item:
				return self._disjoint_set.index(item)
		return None

	def find(self, elem):
		for item in self._disjoint_set:
			if elem in item:
				return self._disjoint_set[self._disjoint_set.index(item)]
		return None

	def union(self, elem1, elem2):
		index_elem1 = self._find_index(elem1)
		index_elem2 = self._find_index(elem2)
		if index_elem1 != index_elem2 and index_elem1 is not None and (index_elem2 is not None):
			self._disjoint_set[index_elem2] = self._disjoint_set[index_elem2] + self._disjoint_set[index_elem1]
			del self._disjoint_set[index_elem1]
		return self._disjoint_set

	def get(self):
		return self._disjoint_set

def graph(n, m, edg=False):
	edges = []
	visited = [0] * n
	g = [list() for _ in range(n + 1)]
	for i in range(m):
		(u, v) = f(1)
		g[u].append(v)
		g[v].append(u)
		if edg:
			edges.append((u, v))
	if edg:
		return (g, visited, edg)
	else:
		return (g, visited)

def bfs(g, visited):
	queue = [1]
	visited[1] = 1
	for u in queue:
		for v in g[u]:
			if visited[v] == 0:
				queue.append(v)
			visited[v] = 1

def dfs(u, g, visited):
	print(u)
	visited[u] = 1
	for v in g[u]:
		if visited[v] == 0:
			dfs(v, g, visited)
n = f()
dl = [0] * (n + 1)
count = 1
for i in range(2, n // 2 + 1):
	st = False
	for j in range(i, n + 1, i):
		if dl[j] == 0:
			dl[j] = count
			st = True
	if st:
		count += 1
for i in range(n // 2 + 1, n + 1):
	if dl[i] == 0:
		dl[i] = count
		count += 1
print(*dl[2:])


def run():
	n = eval(input())
	nums = [0] * (n - 1)
	current = 2
	for i in range(2, n + 1):
		j = i
		enter = False
		while j < n + 1:
			if nums[j - 2] == 0:
				enter = True
				nums[j - 2] = current
			j += i
		if enter:
			current += 1
	for i in range(n - 1):
		if nums[i] == current - 1:
			nums[i] = 1
	print(' '.join(list(map(str, nums))))
run()


n = int(input())
l = [0] * (n + 1)
k = 1
for i in range(2, n + 1):
	if l[i] == 0:
		for j in range(i, n + 1, i):
			l[j] = k
		k += 1
print(*l[2:])


n = int(input())
a = []
for i in range(n + 1):
	a.append(0)
num = 1
count = 2
while count != n + 1:
	if a[count] == 0:
		factor = count
		ind = factor
		while ind <= n:
			a[ind] = num
			ind = ind + factor
		num = num + 1
	count = count + 1
for i in range(2, n + 1):
	print(a[i], end=' ')


def solve(n):
	array = [0] * (n + 1)
	curr = 1
	for i in range(2, n + 1):
		if array[i] == 0:
			j = 1
			while i * j <= n:
				array[i * j] = curr
				j += 1
			curr += 1
	for i in range(2, n + 1):
		print(array[i], end=' ')

def main():
	n = int(input())
	solve(n)
main()


from collections import Counter
import string
import math
import bisect
import sys
from fractions import Fraction

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))

def primeFactors(n):
	primes = []
	while n % 2 == 0:
		primes.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			primes.append(i)
			n = n // i
	if n > 2:
		primes.append(n)
	return primes
primes = []

def SieveOfEratosthenes(n):
	global primes
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
prime = SieveOfEratosthenes(10 ** 5 + 1)
testcases = 1
for _ in range(testcases):
	n = vary(1)
	num = [1] * (n + 1)
	j = 2
	for i in range(3, n + 1):
		if prime[i]:
			num[i] = j
			j += 1
		else:
			primes = primeFactors(i)
			primes.sort()
			num[i] = num[primes[0]]
	print(*num[2:])


from math import *
from collections import Counter, defaultdict, deque
from sys import stdin, stdout
input = stdin.readline
I = lambda : int(input())
M = lambda : map(int, input().split())
LI = lambda : list(map(int, input().split()))
for _ in range(1):
	n = I()
	a = [0] * (n + 1)
	i = 2
	c = 1
	while i <= n:
		if not a[i]:
			for j in range(i, n + 1, i):
				a[j] = c
			c += 1
		i += 1
print(*a[2:])


n = int(input())
arr = [0] * (n + 1)
for i in range(2, n + 1, 2):
	arr[i] = 1
count = 2
for i in range(3, n + 1, 2):
	a = i
	flag = 0
	while a < n + 1:
		if arr[a] == 0:
			arr[a] = count
			flag = 1
		a = a + 2 * i
	if flag == 1:
		count = count + 1
for i in range(2, n + 1):
	print(int(arr[i]), end=' ')


n = int(input())
pr = [2]

def is_prime(x):
	for d in pr:
		if x % d == 0:
			return d
	return 0
print(1, end=' ')
for x in range(3, n + 1):
	d = is_prime(x)
	if d == 0:
		pr.append(x)
		print(len(pr), end=' ')
	else:
		print(pr.index(d) + 1, end=' ')


n = int(input())
arr = [-1 for i in range(n + 1)]
cnt = 1
for i in range(2, n + 1):
	if arr[i] != -1:
		continue
	else:
		j = i
		while j <= n:
			arr[j] = cnt
			j += i
		cnt += 1
print(*arr[2:])


def make_prime_numbers(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n ** 0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(2 * i, n + 1, i):
			is_prime[j] = False
	prime_numbers = [i for i in range(n + 1) if is_prime[i]]
	return prime_numbers
n = int(input())
prime_list = make_prime_numbers(n)
ans = [0] * (n + 1)
for (i, num) in enumerate(prime_list):
	tmp_num = num
	while tmp_num < n + 1:
		ans[tmp_num] = i + 1
		tmp_num += num
print(' '.join(map(str, ans[2:])))


n = int(input())
n += 1
ans = [0] * (n + 1)
num = 1
i = 2
curr = i
while i <= n:
	if ans[i] == 0:
		while curr < n:
			if ans[curr] == 0:
				ans[curr] = num
			curr += i
		i += 1
		curr = i
		num += 1
	else:
		i += 1
		curr = i
print(*ans[2:-1])


n = int(input())
a = [0] * (n + 2)
x = 1
for i in range(2, n + 1):
	if a[i] == 0:
		a[i] = x
		for j in range(i * i, n + 1, i):
			a[j] = x
		x += 1
s = []
for k in range(2, n + 1):
	s.append(a[k])
print(*s)


n = int(input())
ans = [0 for i in range(n + 1)]
cur = 1
p = 2
for i in range(2, n + 1):
	if ans[i] == 0:
		for j in range(i, n + 1, i):
			ans[j] = cur
		cur += 1
print(*ans[2:n + 1])


from math import *
n = int(input())
a = [0 for i in range(n + 1)]
ct = 1
for i in range(2, n + 1):
	if a[i] == 0:
		a[i] = ct
		for j in range(i * i, n + 1, i):
			a[j] = ct
		ct += 1
for i in range(2, n + 1):
	print(a[i], end=' ')
print()


import os
import operator
import sys
import bisect
import _operator
from _collections import defaultdict
from io import BytesIO, IOBase

def inar():
	return [int(k) for k in input().split()]

def power(x, p, m):
	res = 1
	while p:
		if p & 1:
			res = res * x % m
		x = x * x % m
		p >>= 1
	return res

def main():
	n = int(input())
	primes = [1] * (n + 1)
	ans = [0] * (n + 1)
	for i in range(2, int(n ** 0.5) + 1):
		if primes[i] == 1:
			for j in range(i * i, n + 1, i):
				if primes[j] == 1:
					primes[j] = 0
	k = 1
	for i in range(2, int(n ** 0.5) + 1):
		if ans[i] == 0:
			ans[i] = k
			k += 1
			for j in range(i * i, n + 1, i):
				if ans[j] == 0:
					ans[j] = ans[i]
	for i in range(2, n + 1):
		if ans[i] == 0:
			ans[i] = k
			k += 1
	print(*ans[2:n + 1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def SieveOfEratosthenes(n):
	prime = ['TRUE' for i in range(n + 1)]
	p = 2
	t = 1
	while p * p <= n:
		if prime[p] == 'TRUE':
			for i in range(p, n + 1, p):
				prime[i] = t
			t = t + 1
		p += 1
	for p in range(2, n + 1):
		if prime[p] == 'TRUE':
			prime[p] = t
			t = t + 1
	return prime[2:]
n = int(input())
arr = SieveOfEratosthenes(n)
print(' '.join((str(i) for i in arr)))


n = int(input())
s = [-1] * n
ind = 1
cu = 1
while ind < n:
	if s[ind] == -1:
		s[ind::ind + 1] = len(s[ind::ind + 1]) * [cu]
		cu += 1
	ind += 1
for i in s[1:]:
	print(i, end=' ')
print()


prime = [2, 3, 5, 7, 11]
for i in range(12, 100010):
	for j in prime:
		if i % j == 0:
			break
		if j * j > i:
			prime.append(i)
			break
	else:
		prime.append(i)
d = {}
for i in range(1, len(prime) + 1):
	d[prime[i - 1]] = i
n = int(input())
for i in range(2, n + 1):
	if i in d:
		print(d[i], end=' ')
	else:
		for j in range(len(prime)):
			if i % prime[j] == 0:
				print(j + 1, end=' ')
				break


n = int(input())
a = [0, 0, 1] + [0 for i in range(1, n - 1)]
ct = 1
for i in range(2, n + 1):
	if a[i] == 0:
		ct += 1
		a[i] = ct
	for j in range(i * 2, n + 1, i):
		a[j] = a[i]
print(*a[2:])


def primes(n):
	allp = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			allp.append(p)
	return allp
n = int(input())
l = [0] * (n - 1)
k = 1
allp = primes(n + 1)
for i in allp:
	for j in range(i, n + 1, i):
		if l[j - 2] == 0:
			l[j - 2] = k
	k += 1
for i in l:
	print(i, end=' ')


def isPrime(n):
	p = 2
	while p * p <= n:
		if n % p == 0:
			return False
		p += 1
	return True

def nextPrime(n):
	n += 1
	while not isPrime(n):
		n += 1
	return n
n = int(input())
nums = [0] * (n - 1)
p = 2
for i in range(len(nums)):
	m = 1
	while p <= n:
		k = 1
		while k * p <= n:
			if nums[k * p - 2] == 0:
				nums[k * p - 2] = m
			k += 1
		p = nextPrime(p)
		m += 1
for e in nums:
	print(e, end=' ')
print('')


n = int(input())
arr = [0] * (n + 1)
assn = 0
i = 2
while i < n + 1:
	if arr[i] == 0:
		assn += 1
		arr[i] = assn
		j = i
		while j < n + 1:
			arr[j] = arr[i]
			j += i
	print(arr[i], end=' ')
	i += 1


N = int(input())
L = [0] * (N + 1)
ctr = 1
for i in range(2, N + 1):
	if L[i] == 0:
		j = i
		while j < N + 1:
			L[j] = ctr
			j += i
		ctr += 1
print(*L[2:])


n = int(input())
a = [0] * 100001
cnt = 1
for i in range(2, n + 1):
	if a[i] == 0:
		for j in range(i, n + 1, i):
			if a[j] == 0:
				a[j] = cnt
		cnt += 1
res = []
for i in range(1, n):
	res.append(str(a[i + 1]))
print(' '.join(res))


n = int(input())

def get_prime(n):
	is_p = [0] * (n + 1)
	prime = []
	for i in range(2, n + 1):
		if is_p[i] == 0:
			prime.append(i)
		for j in prime:
			if i * j >= n:
				break
			is_p[i * j] = 1
			if i % j == 0:
				break
	return prime

def solve(n):
	res = [0] * (n + 1)
	prime = get_prime(n)
	seq = 1
	for x in prime:
		tmp = x
		while x < n + 1:
			if res[x] == 0:
				res[x] = seq
			x += tmp
		seq += 1
	return ' '.join(map(str, res[2:]))
print(solve(n))


n = int(input())
arr = [None] * (n + 3)
cnt = 1
for i in range(2, n + 1):
	if not arr[i]:
		for j in range(i, n + 1, i):
			if not arr[j]:
				arr[j] = cnt
		cnt += 1
print(' '.join(map(str, arr[2:n + 1])))


from math import *
n = int(input())
ar = [0, 0]
k = 1
for i in range(1, n + 1):
	ar.append(0)
for i in range(2, n + 1, 1):
	if ar[i] == 0:
		for j in range(i, n + 1, i):
			ar[j] = k
		k = k + 1
for i in range(2, n + 1):
	print(ar[i], end=' ')


n = int(input())
a = list(range(n + 1))
is_know = [False] * (n + 1)
i = 2
k = 1
while i < n + 1:
	while i < n + 1:
		if not is_know[i]:
			break
		i += 1
	for m in range(1, n // i + 1):
		a[m * i] = k
		is_know[m * i] = True
	k += 1
print(*a[2:])


n = int(input())
a = [0 for _ in range(n)]
k = 0
for d in range(2, n + 1):
	if a[d - 1] == 0:
		k += 1
		for i in range(1, n // d + 1):
			a[d * i - 1] = k
print(*a[1:])


n = int(input())
arr = [0 for x in range(n + 1)]
c = 0
change = 1
for i in range(2, n + 1):
	if change:
		c += 1
	next = i
	change = 0
	while next <= n:
		if arr[next] == 0:
			arr[next] = c
			change = 1
		next += i
print(*arr[2:])


n = int(input())
a = [0] * 100005
cnt = 1
for i in range(2, n + 1):
	if a[i] == 0:
		a[i] = cnt
		cnt += 1
		for j in range(i, n + 1, i):
			a[j] = a[i]
	print(a[i], end=' ')


import sys
import math
RI = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def seive():
	global ite
	ans[2] = ite
	for i in range(4, n + 1, 2):
		prime[i] = False
		ans[i] = ite
	ite += 1
	p = 3
	while p * p <= n + 1:
		if prime[p]:
			ans[p] = ite
			for j in range(p * p, n + 1, p):
				prime[j] = False
				ans[j] = ite
			ite += 1
		p += 2
n = int(ri())
ite = 1
ans = [0] * (n + 1)
prime = [True] * (n + 1)
seive()
ans = ans[2:]
for i in range(len(ans)):
	if ans[i] == 0:
		ans[i] = ite
		ite += 1
print(*ans)


from math import ceil, sqrt
N = int(input())
Visited = [False] * (N + 3)
Ans = [-1] * (N + 3)
mark = 1
for i in range(2, int(ceil(sqrt(N))) + 1):
	if Visited[i] == False:
		Ans[i] = mark
		for j in range(2 * i, N + 3, i):
			if Ans[j] == -1:
				Ans[j] = mark
				Visited[j] = True
		mark += 1
for x in range(2, N + 1):
	if Ans[x] == -1:
		Ans[x] = mark
		mark += 1
print(*Ans[2:N + 1])


def sieve(n):
	arr = [1] * (n + 1)
	(arr[0], arr[1]) = (0, 0)
	for i in range(2, n + 1):
		if arr[i] == 1:
			arr[2 * i::i] = [0 for _ in range(len(arr[2 * i::i]))]
	return arr

def min_prime_factors(n):
	factors = []
	d = 2
	while d * d <= n:
		while n > 1:
			while n % d == 0:
				factors.append(d)
				n = n / d
			d += 1
	return factors[-1]

def solve():
	N = int(input())
	prime = sieve(N + 1)
	result = [1] * (N + 1)
	result[3::2] = [2 for _ in range(len(result[3::2]))]
	last = 3
	for i in range(5, N + 1, 2):
		if prime[i]:
			result[i::i] = [last for _ in range(len(result[i::i]))]
			last += 1
	print(' '.join(map(str, result[2:])))
solve()


import math
n = int(input())

def isprime(n):
	for i in range(2, round(math.sqrt(n)) + 1):
		if n % i == 0:
			return i
	return -1
a = []
for i in range(2, n + 1):
	a.append(i)
inc = 1
for i in a:
	res = isprime(i)
	if res != -1:
		a[i - 2] = a[res - 2]
	else:
		a[i - 2] = inc
		inc += 1
print(' '.join((str(i) for i in a)))


n = int(input())
l = [True, True] + [False for i in range(2, n + 1)]
k = [0, 0] + [0 for i in range(2, n + 1)]
c = 0
for i in range(2, n + 1):
	if l[i] is False:
		c += 1
		for j in range(i, n + 1, i):
			l[j] = True
			k[j] = c
print(*k[2:])


from math import ceil

def is_prime(num):
	sq = ceil(num ** (1 / 2))
	if num == 2:
		return True
	for i in range(2, sq + 1):
		if num % i == 0:
			return False
	return True

def first_divisor(num):
	for i in range(2, num):
		if num % i == 0:
			return i
n = int(input())
counter = 0
lst_of_nums = []
for i in range(2, n + 1):
	if is_prime(i):
		counter += 1
		print(counter, end=' ')
		lst_of_nums.append(counter)
	else:
		FD = first_divisor(i)
		print(lst_of_nums[FD - 2], end=' ')
		lst_of_nums.append(lst_of_nums[FD - 2])


n = int(input())
a = [0] * (n + 1)
clr = 1
num = 2
while num * num <= n:
	if a[num] == 0:
		a[num] = clr
		k = num * num
		while k <= n:
			a[k] = clr
			k += num
		clr += 1
	num += 1
b = a[2:]
for i in range(len(b)):
	if b[i] == 0:
		b[i] = clr
		clr += 1
print(*b)


n = int(input())
prime = [True] * (n + 1)
prime[0] = prime[1] = False
color = [0] * (n - 1)
next = 1
for i in range(2, n + 1):
	if prime[i]:
		color[i - 2] = next
		if i ** 2 <= n:
			for j in range(i ** 2, n + 1, i):
				prime[j] = False
				color[j - 2] = next
		next += 1
print(*color)


n = int(input())
esph = [n] * (n + 1)
top = 1
for i in range(2, n + 1):
	inc = False
	esph[i] = min(esph[i], top)
	inc = inc or esph[i] == top
	for k in range(2 * i, n + 1, i):
		esph[k] = min(esph[k], top)
		inc = inc or esph[k] == top
	if inc:
		top += 1
print(' '.join(map(str, esph[2:])))


def color(n):
	(lst, count) = ([0] * (n - 1), 0)
	for i in range(2, n + 1):
		if lst[i - 2] == 0:
			count += 1
			lst[i - 2] = count
			for j in range(i + i, n + 1, i):
				lst[j - 2] = count
	return lst
print(*color(int(input())))


import sys
input = sys.stdin.readline

class Problem:

	def __init__(self):
		pass

	def solve(self):
		print(self._solve())

	def _solve(self):
		n = int(input())
		done = [0] * (n + 1)
		v = 1
		for i in range(2, n + 1):
			if done[i]:
				continue
			k = 1
			while k * i <= n:
				done[k * i] = v
				k += 1
			v += 1
		return ' '.join((str(x) for x in done[2:]))

def main():
	problem = Problem()
	problem.solve()
main()


from math import *
n = int(input())
a = [0] * (n + 1)
now = 1
for i in range(2, n + 1):
	if a[i] == 0:
		a[i] = now
		tmp = i
		while tmp <= n:
			if a[tmp] == 0:
				a[tmp] = now
			tmp += i
		now += 1
print(*a[2:])


from collections import defaultdict as dd

def get_primes(n):
	l = []
	pr = [True for i in range(n + 1)]
	j = 2
	while j * j <= n:
		if pr[j] == True:
			for i in range(j * j, n + 1, j):
				pr[i] = False
		j += 1
	for j in range(2, n):
		if pr[j]:
			l.append(j)
	return l
n = int(input())
c = 1
p = get_primes(n + 1)
x = 1
l = [0] * (n - 1)
for i in p:
	for j in range(i, n + 1, i):
		if l[j - 2] == 0:
			l[j - 2] = x
	x += 1
print(*l)


import math
n = int(input())
s = []
count = 1

def isprime(i, count):
	x = int(math.sqrt(i)) + 1
	for y in range(2, x + 1):
		if i % y == 0:
			return y - 1
	count += 1
	return count
for i in range(2, n + 1):
	z = isprime(i, count)
	if count < z:
		count += 1
		s.append(str(z))
	elif z > len(s) - 1:
		s.append(str(z))
	else:
		s.append(str(s[z - 1]))
print(' '.join(s))


primes = [2]

def tryp(num):
	bound = num ** 0.5
	for p in primes:
		if p > bound:
			primes.append(num)
			return
		if num % p == 0:
			return
for num in range(3, 100000, 2):
	tryp(num)
num = 1 + int(input())
data = [0] * num
c = 0
for p in primes:
	c += 1
	if p >= num:
		break
	for i in range(p, num, p):
		if data[i] == 0:
			data[i] = c
data = data[2:]
[print(a, end=' ') for a in data]


n = int(input())
r = [0] * (n - 1)
c = 1
for i in range(2, n + 1):
	if r[i - 2] == 0:
		j = i
		for j in range(j, n + 1, j):
			r[j - 2] = c
		c += 1
print(*r)


sieve = [0] * (10 ** 5 + 10)
prime = []
for i in range(2, 10 ** 5 + 10):
	j = 2 * i
	while j < len(sieve):
		sieve[j] = -1
		j += i
for i in range(2, len(sieve)):
	if sieve[i] == 0:
		prime.append(i)
from sys import stdout
ans = [0] * (10 ** 5 + 10)
n = int(input())
for i in range(0, len(prime)):
	j = prime[i]
	while j < len(ans):
		if ans[j] != 0:
			j += prime[i]
			continue
		ans[j] = i + 1
		j += prime[i]
for i in range(2, n + 1):
	stdout.write(str(ans[i]) + ' ')


import sys
import math
import itertools
import collections

def ii():
	return int(input())

def mi():
	return map(int, input().split())

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

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def wr(arr):
	return ' '.join(map(str, arr))

def revn(n):
	return str(n)[::-1]

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base):
	newnumber = 0
	while number > 0:
		newnumber += number % base
		number //= base
	return newnumber

def cdiv(n, k):
	return n // k + (n % k != 0)
p = sieve(10 ** 5)
n = ii()
ans = []
j = 1
for i in range(2, n + 1, 1):
	if prime(i):
		ans.append(j)
		j += 1
	else:
		for nu in p:
			if i % nu == 0:
				ans.append(p.index(nu) + 1)
				break
print(wr(ans))


def main():
	prime = [2]
	for i in range(3, 318):
		check = True
		for j in prime:
			check = check and i % j != 0
		if check:
			prime.append(i)
	now = 67
	mas = [-1, -2]
	n = int(input())
	for i in range(2, n + 1):
		for jj in range(66):
			j = prime[jj]
			if i % j == 0:
				print(jj + 1, end=' ')
				break
		else:
			print(now, end=' ')
			now += 1
main()


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	return prime
	for p in range(2, n):
		if prime[p]:
			print(p)
n = int(input())
primes = SieveOfEratosthenes(n)
start = 1
pr = {}
for p in range(2, n + 1):
	if primes[p]:
		print(start, end=' ')
		pr[p] = start
		start += 1
	else:
		for i in range(2, int(p / 2) + 1):
			if p % i == 0:
				print(pr[i], end=' ')
				break


n = int(input())
prime = [0, 0] + [1] * 99999
ans = [0] * 100001
newcnt = 1
for i in range(2, n + 1):
	if prime[i] == 0:
		continue
	ans[i] = newcnt
	t = 2
	while i * t <= n:
		prime[i * t] = 0
		ans[i * t] = newcnt
		t += 1
	newcnt += 1
print(*ans[2:n + 1])


n = int(input())
a = [0 for i in range(n + 1)]
cnt = 0
for i in range(2, n + 1):
	if not a[i]:
		cnt += 1
		for j in range(i, n + 1, i):
			if not a[j]:
				a[j] = cnt
print(' '.join((str(i) for i in a[2:])))


N = int(input())
primes = [2]
l = [1] * (N - 1)
for num in range(3, N + 1, 2):
	isprime = True
	rt = int(num ** 0.5) + 1
	for i in range(len(primes)):
		if primes[i] > rt:
			break
		if num % primes[i] == 0:
			l[num - 2] = i + 1
			isprime = False
			break
	if isprime:
		primes.append(num)
		l[num - 2] = len(primes)
print(' '.join((str(i) for i in l)))


import math as m
import collections as clt
number_of_elements = 0
arr = []

def Input(number_of_elements):
	number_of_elements = int(input())
	return number_of_elements

def Is_prime(number):
	for index in range(2, int(m.sqrt(number) + 1)):
		if number % index == 0:
			return 0
	return 1

def Smallest_divisor(number):
	for index in range(2, int(m.sqrt(number) + 1)):
		if number % index == 0:
			return index
	return number

def Processing(number_of_elements):
	arr.append(0)
	arr.append(0)
	count = 0
	for index in range(2, number_of_elements + 1):
		if Is_prime(index):
			count += 1
			arr.append(count)
		else:
			arr.append(0)
	for index in range(2, number_of_elements + 1):
		if arr[index] == 0:
			arr[index] = arr[Smallest_divisor(index)]
	for index in range(2, number_of_elements + 1):
		print(arr[index], end=' ')
number_of_elements = Input(number_of_elements)
number_of_elements = Processing(number_of_elements)


n = int(input())
lis = [0] * n
lis.insert(0, 0)
c = 1
for i in range(2, n + 1):
	if lis[i] == 0:
		for j in range(i, n + 1, i):
			if lis[j] == 0:
				lis[j] = c
		c += 1
for i in lis[2:]:
	print(i, end=' ')
print()


entrada = int(input())
array = [None] * 100050
x = 0
i = 2
while i <= entrada:
	if not array[i]:
		x += 1
		j = 1
		while j * i <= entrada:
			if not array[i * j]:
				array[i * j] = x
			j += 1
	i += 1
saida = ''
for k in range(2, entrada):
	saida += str(array[k]) + ' '
saida += str(array[entrada])
print(saida)


def solve():
	n = int(input())
	l = [0] * (n + 1)
	counter = 1
	for i in range(2, n + 1):
		if l[i] == 0:
			for j in range(1, n // i + 1):
				l[i * j] = counter
			counter += 1
	print(*l[2:])
solve()


from __future__ import division, print_function
import sys
if sys.version_info.major == 2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return map(int, sys.stdin.readline().split())

def input():
	return sys.stdin.readline().strip()

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

	def primes_sieve(limit):
		a = [True] * limit
		a[0] = a[1] = False
		for (i, isprime) in enumerate(a):
			if isprime:
				yield i
				for n in range(i * i, limit, i):
					a[n] = False
	primes = list(primes_sieve(n + 1))
	arr = [0] * (n + 1)
	curr = 1
	for i in range(2, n + 1):
		if arr[i] != 0:
			continue
		j = i
		while j <= n:
			arr[j] = curr
			j += i
		curr += 1
	print(*arr[2:])
main()


from collections import defaultdict as dd
from itertools import combinations
import math
import heapq

def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return map(int, input().split())

def lm():
	return list(map(int, input().split()))
n = nn()
current = 1
taken = [0] * (n - 1)
val = 2
while val * val <= n:
	if taken[val - 2] == 0:
		c = 1
		while c * val <= n:
			taken[c * val - 2] = current
			c += 1
		current += 1
	val += 1
for i in range(len(taken)):
	if taken[i] == 0:
		taken[i] = current
		current += 1
print(*taken)


n = int(input())
is_prime = [True] * (n + 1)
vals = [0] * (n + 1)
(is_prime[0], is_prime[1]) = (False, False)
primes = 0
for i in range(2, n + 1):
	if is_prime[i]:
		primes += 1
		for j in range(i, n + 1, i):
			is_prime[j] = False
			if vals[j] == 0:
				vals[j] += primes
for i in range(2, n + 1):
	print(vals[i], end=' ')


n = int(input())
p = [0] * (n + 1)
b = []
ans = [0] * (n + 1)
for i in range(2, n + 1):
	if p[i] == 0:
		b.append(i)
		ans[i] = len(b)
		for j in range(2 * i, n + 1, i):
			p[j] = 1
			ans[j] = ans[i]
print(*ans[2:])


n = int(input())
has = [0] * (n + 1)
for i in range(2, n + 1):
	if has[i] == 0:
		for j in range(2 * i, n + 1, i):
			has[j] = i
co = 0
for i in range(2, n + 1):
	if has[i] == 0:
		co += 1
k = 1
no = [1] * (n + 1)
for i in range(2, n + 1):
	if has[i] == 0:
		print(k, end=' ')
		no[i] = k
		k += 1
	else:
		print(no[has[i]], end=' ')


n = 100000
arr = [0 for i in range(n + 1)]
arr[1] = 1
for i in range(2, n + 1):
	if arr[i] == 0:
		arr[i] = i
		for j in range(2 * i, n + 1, i):
			if arr[j] == 0:
				arr[j] = i
count = 1
for i in range(2, n + 1):
	if arr[i] == i:
		arr[i] = count
		count += 1
	else:
		arr[i] = arr[arr[i]]
t = int(input())
for i in range(2, t + 1):
	print(arr[i], end=' ')


import sys
input = sys.stdin.readline
n = int(input())
ANS = [0] * (n + 1)
now = 1
for i in range(2, n + 1):
	if ANS[i] != 0:
		continue
	else:
		for j in range(i, n + 1, i):
			if ANS[j] == 0:
				ANS[j] = now
		now += 1
print(*ANS[2:])


import sys

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return map(int, sys.stdin.readline().split())

def input():
	return sys.stdin.readline().strip()

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

	def primes_sieve(limit):
		a = [True] * limit
		a[0] = a[1] = False
		for (i, isprime) in enumerate(a):
			if isprime:
				yield i
				for n in range(i * i, limit, i):
					a[n] = False
	primes = list(primes_sieve(n + 1))
	arr = [0] * (n + 1)
	curr = 1
	for i in range(2, n + 1):
		if arr[i] != 0:
			continue
		j = i
		while j <= n:
			arr[j] = curr
			j += i
		curr += 1
	print(*arr[2:])
main()


def SieveOfEratosthenes(n):
	prime = [0 for i in range(n + 1)]
	p = 2
	m = 1
	while p <= n:
		if prime[p] == 0:
			for i in range(p, n + 1, p):
				prime[i] = m
			m += 1
		p += 1
	print(*prime[2:])
SieveOfEratosthenes(int(input()))


def isPrime(n):
	if n == 2 or n == 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	w = 2
	sqN = int(pow(n, 0.5))
	while i <= sqN:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True
n = int(input().strip())
arr = [0] * (n + 1)
c = 1
for i in range(2, n + 1):
	if isPrime(i):
		arr[i] = c
		for j in range(i + i, n + 1, i):
			if not arr[j]:
				arr[j] = c
		c += 1
print(*arr[2:])


n = int(input())
n += 1
p = [True] * n
pr = [1] * n
m = 1
for k in range(2, n):
	if p[k]:
		for i in range(k, n, k):
			p[i] = False
			pr[i] = m
		m += 1
print(' '.join(map(str, pr[2:])))


n = int(input())
ans = [0 for i in range(0, n + 10)]
c = 1
for i in range(2, n + 1):
	if not ans[i]:
		ans[i] = c
		c += 1
		j = i
		while j <= n:
			ans[j] = ans[i]
			j += i
	print(ans[i], end=' ')


simp = [2]
n = int(input())
arr = [-1] * (n + 1)
arr[2] = 1
curr = 2
for i in range(3, n + 1):
	for s in simp:
		if s > i ** 0.5:
			simp.append(i)
			arr[i] = curr
			curr += 1
			break
		elif (i / s).is_integer():
			arr[i] = arr[s]
			break
print(*arr[2:])


n = int(input())
prime = [True for i in range(n + 1)]
p = 2
while p * p <= n:
	if prime[p] == True:
		for i in range(p * 2, n + 1, p):
			prime[i] = False
	p += 1
prime[0] = False
prime[1] = False
allp = []
for p in range(n + 1):
	if prime[p]:
		allp.append(p)
res = [1] * (n + 1)
counter = 1
for elem in allp:
	i = 0
	while i <= n:
		res[i] = counter
		i += elem
	counter += 1
print(*res[2:])


n = int(input())
a = [0] * (n + 1)
c = 1
for i in range(2, n + 1):
	if a[i] != 0:
		continue
	for j in range(i, n + 1, i):
		if a[j] == 0:
			a[j] = c
	c += 1
print(*a[2:])


n = int(input())
c = 1
l = [1]
for i in range(3, n + 1):
	prime = True
	for j in range(2, int(i ** 0.5) + 1):
		if i % j == 0:
			prime = False
			break
	if prime == True:
		c += 1
		l.append(c)
	else:
		l.append(l[j - 2])
for i in l:
	print(i, end=' ')


n = int(input())
ans = [0] * (n + 1)
ai = 1
prime = [True] * (n + 1)
p = 2
while p <= n:
	if prime[p]:
		for i in range(p, n + 1, p):
			prime[i] = False
			ans[i] = ai
		ai += 1
	p += 1
print(' '.join(map(str, ans[2:])))


from collections import deque
n = int(input())
pr = [0] * (1 + n)
p = [0]

def mind(x):
	for i in range(2, int(x ** 0.5) + 1):
		if x % i == 0:
			return pr[i]
	p.append(p[-1] + 1)
	pr[x] = p[-1]
	return p[-1]
a = []
b = []
for i in range(2, n + 1):
	t = mind(i)
	a.append(t)
print(*a)

def gcd(x, y):
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y


x = int(input())
start = 1
lol = [-1 for _ in range(x + 1)]
for i in range(2, x + 1):
	used = False
	for j in range(i, x + 1, i):
		if lol[j] == -1:
			lol[j] = start
			used = True
	if used:
		start += 1
print(*lol[2:])


n = int(input())
t = 1
ans = [0] * (n + 2)
for i in range(2, n + 1):
	if ans[i] == 0:
		for j in range(i, n + 1, i):
			if ans[j] == 0:
				ans[j] = t
		t += 1
for i in range(2, n + 1):
	print(ans[i], end=' ')


n = int(input())
prime = [1] * (n + 1)
a = 1
x = [0] * (n + 1)
for i in range(2, n + 1):
	if prime[i]:
		x[i] = a
		for j in range(2 * i, n + 1, i):
			prime[j] = False
			x[j] = a
		a += 1
print(*x[2:])


n = int(input())
ans = [0] * (10 ** 5 + 100)
c = 1
for i in range(2, n + 1):
	if not ans[i]:
		ans[i] = c
		for j in range(i, n + 1, i):
			ans[j] = ans[i]
		c += 1
x = ans[2:n + 1]
for i in x:
	print(i, end=' ')


n = int(input())
sie = [10 ** 9] * (n + 1)
sie[0] = 0
sie[1] = 0
ans = 1
for i in range(2, n + 1):
	if sie[i] == 10 ** 9:
		sie[i] = ans
		for j in range(i, n + 1, i):
			sie[j] = ans
		ans += 1
print(*sie[2:])


N = int(input())
M = [0] * 100010
c = 0
for i in range(2, N + 1):
	if M[i] == 0:
		c += 1
		M[i] = c
		for j in range(i, N + 1, i):
			M[j] = c
for i in range(2, N + 1):
	print(M[i], end=' ')
print()


def SieveOfEratosthenes(n, ans):
	c = 1
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			ans[p] = c
			for i in range(p * p, n + 1, p):
				prime[i] = False
				ans[i] = c
			c += 1
		p += 1
	return c
n = int(input())
ans = [0] * (n + 1)
c = SieveOfEratosthenes(n, ans)
for i in range(2, n + 1):
	if ans[i] == 0:
		ans[i] = c
		c += 1
print(' '.join((str(x) for x in ans[2:])))


n = int(input())
lst = [0] * (n + 1)
counter = 1
for i in range(2, n + 1):
	if lst[i] == 0:
		lst[i] = counter
		counter = counter + 1
		j = 2
		while i * j < n + 1:
			lst[i * j] = lst[i]
			j = j + 1
	else:
		pass
print(*lst[2:])


def pr(a):
	ans = ''
	for i in range(len(a)):
		ans += str(a[i]) + ' '
	return ans

def pros(a):
	for i in range(2, int(a ** 0.5) + 1):
		if a % i == 0:
			return False
	return True

def mini(a):
	for i in range(2, int(a)):
		if a % i == 0:
			return i
n = int(input())
a = 2
lis = []
for i in range(2, n + 1):
	if i % 2 == 0:
		lis.append(1)
	elif pros(i):
		lis.append(a)
		a += 1
	else:
		lis.append(lis[mini(i) - 2])
print(pr(lis))


n = int(input())
a = [0] * (n - 1)
b = list(range(2, n + 1))
now = 0
for index in range(n - 1):
	if b[index] != 0:
		b[index] = 0
		now += 1
		for j in range(index, n - 1, index + 2):
			a[j] = now
			b[j] = 0
print(*a)


n = int(input())
a = [0] * (n + 1)
count = 1
for i in range(2, n + 1):
	if a[i] == 0:
		j = i
		while j < n + 1:
			a[j] = count
			j += i
		count += 1
for i in range(n - 1):
	print(a[i + 2], end=' ')


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

def is_prime(v):
	for t in range(2, int(math.sqrt(v)) + 1):
		if not v % t:
			return t
	return 0
a = []
i = 1
for t in range(2, n + 1):
	if not t % 2:
		a.append(1)
	else:
		s = is_prime(t)
		if s:
			a.append(d[s])
			d[t] = d[s]
		else:
			i += 1
			d[t] = i
			a.append(i)
print(' '.join(map(str, a)))


n = int(input())
p = [0] * (n + 1)
a = [0] * (n + 1)
x = 1
for i in range(2, n + 1):
	for j in range(i, n + 1, i):
		if p[j] == 0:
			p[j] = i
for i in range(2, n + 1):
	if a[p[i]] == 0:
		a[p[i]] = x
		x += 1
	print(a[p[i]], end=' ')


N = int(input())

def primes(M):
	is_prime = [-1 for _ in range(M + 1)]
	for m in range(2, M + 1):
		if is_prime[m] == -1:
			is_prime[m] = 1
			l = 2
			while m * l <= M:
				is_prime[m * l] = 0
				l += 1
	primes = []
	for p in range(2, M + 1):
		if is_prime[p] == 1:
			primes.append(p)
	return primes
P = primes(N)
ans = [None] * (N + 1)
for (i, p) in enumerate(P):
	k = p
	while k <= N:
		if ans[k] is None:
			ans[k] = i + 1
		k += p
for n in range(2, N + 1):
	print(ans[n], end=' ')
print()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

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

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def IF(c, t, f):
	return t if c else f

def YES(c):
	return IF(c, 'YES', 'NO')

def Yes(c):
	return IF(c, 'Yes', 'No')

class Prime:

	def __init__(self, n):
		self.M = m = int(math.sqrt(n)) + 10
		self.A = a = [True] * m
		a[0] = a[1] = False
		self.T = t = [2]
		for j in range(4, m, 2):
			a[j] = False
		for i in range(3, m, 2):
			if not a[i]:
				continue
			t.append(i)
			for j in range(i * i, m, i):
				a[j] = False
		self.ds_memo = {}
		self.ds_memo[1] = set([1])

	def is_prime(self, n):
		return self.A[n]

	def division(self, n):
		d = collections.defaultdict(int)
		for c in self.T:
			while n % c == 0:
				return c
				d[c] += 1
				n //= c
			if n < 2:
				break
		return n
		if n > 1:
			d[n] += 1
		return d.items()

def main():
	t = 1
	rr = []
	for _ in range(t):
		n = I()
		pr = Prime(10 ** 10)
		t = 1
		d = {}
		r = []
		for i in range(2, n + 1):
			if pr.is_prime(i):
				r.append(t)
				d[i] = t
				t += 1
			else:
				k = pr.division(i)
				r.append(d[k])
		rr.append(JA(r, ' '))
	return JA(rr, '\n')
print(main())


n = int(input())
numbers = list(range(2, n + 1))
arr = [0] * (n - 1)
counter = 0
for number in numbers:
	if number != 0:
		counter += 1
		arr[number - 2] = counter
		for candidate in range(2 * number, n + 1, number):
			numbers[candidate - 2] = 0
			arr[candidate - 2] = counter
print(*arr)


n = int(input())
l = [0] * (n - 1)
v = 0
for i in range(n - 1):
	if l[i] == 0:
		v += 1
		for j in range(i, n - 1, i + 2):
			if l[j] == 0:
				l[j] = v
for i in l:
	print(i, end=' ')
print()


a = int(input())
ar = []
for i in range(a + 1):
	ar.append(-1)
j = 0
c = 0
for i in range(a + 1):
	if i > 1 and ar[i] == -1:
		c += 1
		j = 0
		while j + i < a + 1:
			j = j + i
			if ar[j] == -1:
				ar[j] = c
for i in range(a + 1):
	if i > 1:
		print(ar[i], end=' ')


from sys import *
from math import *
n = int(stdin.readline())
a = []
j = 2
for i in range(2, n + 1):
	if i % 2 == 0:
		a.append(1)
	else:
		f = 0
		for k in range(2, int(sqrt(i)) + 1):
			if i % k == 0:
				f = 1
				break
		if f == 0:
			a.append(j)
			j += 1
		else:
			a.append(a[k - 2])
print(*a)


import sys
input = sys.stdin.readline
from collections import *
n = int(input())
ans = [0] * (n + 1)
now = 1
for i in range(2, n + 1):
	if ans[i] == 0:
		for j in range(i, n + 1, i):
			if ans[j] == 0:
				ans[j] = now
		now += 1
print(*ans[2:])


n = int(input())
a = [0] * (n - 1)
j = 1
for (i, aa) in enumerate(a):
	step = i + 2
	if aa != 0:
		continue
	a[i] = j
	for t in range(i + step, n - 1, step):
		if a[t] == 0:
			a[t] = j
	j += 1
print(*a)


n = int(input())
a = [0] * (n + 3)
b = [0] * (n + 3)
for i in range(2, n + 1):
	if a[i] == 0:
		for j in range(i, n + 1, i):
			a[j] = i
x = 1
for i in range(2, n + 1):
	if a[i] == i:
		b[i] = x
		x += 1
for i in range(2, n):
	print(b[a[i]], end=' ')
print(b[a[n]])


def is_prime(n):
	if n == 2 or n == 3:
		return True
	if n < 2 or n % 2 == 0:
		return False
	if n < 9:
		return True
	if n % 3 == 0:
		return False
	r = int(n ** 0.5)
	f = 5
	while f <= r:
		if n % f == 0:
			return False
		if n % (f + 2) == 0:
			return False
		f += 6
	return True
import math
n = int(input())
c = 2
l = []
for i in range(n - 1):
	if i % 2 == 0:
		l += [1]
	elif is_prime(i + 2) or i == 1:
		l += [c]
		c += 1
	else:
		j = 2
		while (i + 2) % j != 0:
			j += 1
		l += [l[j - 2]]
for x in l:
	print(x, end=' ')
print()


import collections
import functools
import math
import sys

def In():
	return map(int, sys.stdin.readline().split())
input = sys.stdin.readline
import functools
import math
import sys

def In():
	return map(int, sys.stdin.readline().split())
input = sys.stdin.readline

def eb():
	n = int(input())
	l = [0] * (n + 1)
	cur = 1
	for i in range(2, n + 1):
		if not l[i]:
			for step in range(i, n + 1, i):
				l[step] = cur
			cur += 1
	l.pop(0)
	l.pop(0)
	print(*l)
eb()


N = int(input())
num = [0] * (N + 1)
import itertools

def erat2():
	D = {}
	yield 2
	for q in itertools.islice(itertools.count(3), 0, None, 2):
		p = D.pop(q, None)
		if p is None:
			D[q * q] = q
			yield q
		else:
			x = p + q
			while x in D or not x & 1:
				x += p
			D[x] = p

def get_primes_erat(n):
	return list(itertools.takewhile(lambda p: p < n, erat2()))
cur = 0
for prime in get_primes_erat(N + 1):
	cur += 1
	for i in range(prime, N + 1, prime):
		num[i] = cur
ans = [str(x) for x in num][2:]
print(' '.join(ans))


import sys, math, string
input = sys.stdin.readline
from collections import deque
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
n = int(input())

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	a = [1] * (n + 1)
	p = 2
	c = 1
	while p <= n:
		if prime[p] == True:
			a[p] = c
			for i in range(p * 2, n + 1, p):
				prime[i] = False
				a[i] = c
			c += 1
		p += 1
	for i in range(2, n + 1):
		print(a[i], end=' ')
SieveOfEratosthenes(n)


import math
n = int(input())
count = 2
ans = [1]
for i in range(3, n + 1):
	prime = True
	c = min(math.ceil(math.sqrt(i)), i - 1) + 1
	for j in range(2, c):
		if i % j == 0:
			prime = False
			ans.append(ans[j - 2])
			break
	if prime == True:
		ans.append(count)
		count += 1
for i in ans:
	print(i, end=' ')


import math
from decimal import Decimal

def na():
	n = int(input())
	b = [int(x) for x in input().split()]
	return (n, b)

def nab():
	n = int(input())
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	return (n, b, c)

def dv():
	(n, m) = map(int, input().split())
	return (n, m)

def dva():
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	return (n, m, b)

def eratosthenes(n):
	sieve = list(range(n + 1))
	for i in sieve:
		if i > 1:
			for j in range(i + i, len(sieve), i):
				sieve[j] = 0
	return sorted(set(sieve))

def nm():
	n = int(input())
	b = [int(x) for x in input().split()]
	m = int(input())
	c = [int(x) for x in input().split()]
	return (n, b, m, c)

def dvs():
	n = int(input())
	m = int(input())
	return (n, m)

def ist(x):
	d = 1
	while d < x:
		d *= 2
	return d == x
n = int(input())
m = [0] * 100010
c = 0
for i in range(2, n + 1):
	if m[i] == 0:
		c += 1
		m[i] = c
		for j in range(i, n + 1, i):
			m[j] = c
for i in range(2, n + 1):
	print(m[i], end=' ')


n = int(input())
ans = [0] * (n + 1)
last = 1
for i in range(2, n + 1):
	if ans[i] != 0:
		continue
	for j in range(i, n + 1, i):
		ans[j] = last
	last += 1
for i in range(2, n + 1):
	print(ans[i], end=' ')


def generate(n):
	l = [0 for j in range(n + 1)]
	p = 2
	prime = 1
	while p * p <= n:
		if l[p] == 0:
			l[p] = prime
			prime = prime + 1
			for i in range(p * p, n + 1, p):
				l[i] = l[p]
		p = p + 1
	l = l[2:]
	for k in range(0, len(l)):
		if l[k] == 0:
			l[k] = prime
			prime = prime + 1
	print(*l)
t = int(input())
generate(t)


n = int(input())
l = []
for i in range(n + 1):
	l.append(-1)
f = 2
counter = 0
while f <= n:
	if l[f] == -1:
		counter += 1
	for i in range(f, n + 1, f):
		if l[i] == -1:
			l[i] = counter
	f += 1
st = ''
for i in range(2, n + 1):
	st += str(l[i]) + ' '
print(st)


import math

def isPrime(n):
	l = 0
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			l += 1
			break
	if l == 0:
		return True
	else:
		return False

def lowest_divisor(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return i
n = int(input())
a = [0] * (n - 1)
p = 2
for i in range(len(a)):
	if i % 2 == 0:
		a[i] = 1
	elif isPrime(i + 2):
		a[i] = p
		p += 1
	else:
		k = lowest_divisor(i + 2)
		a[i] = a[k - 2]
print(*a)


n = int(input())
a = 1
numeros = [0] * (n + 1)
raiz = n ** 0.5 + 2
for i in range(2, n + 1):
	if numeros[i] == 0:
		numeros[i] = a
		if i < raiz:
			for j in range(i * i, n + 1, i):
				numeros[j] = a
		a += 1
print(numeros[2], end='')
for i in range(3, n + 1):
	print(' ', end='')
	print(numeros[i], end='')
print()


n = int(input()) + 1
ret = [None] * n
cur = 1
num = 2
while num < n:
	incremet = 0
	for i in range(num, n, num):
		if not ret[i]:
			ret[i] = cur
			incremet = 1
	num += 1
	cur += incremet
print(*ret[2:])


n = int(input())
A = [0 for _ in range(n - 1)]
for i in range(2, n + 1, 2):
	A[i - 2] = 1
cont = 2
for i in range(3, n + 1, 2):
	if A[i - 2] == 0:
		for j in range(i, n + 1, i):
			if A[j - 2] == 0:
				A[j - 2] = cont
		cont += 1
print(*A)


def SieveOfEratosthenes(n):
	prime = [0 for i in range(n + 1)]
	p = 2
	x = 0
	while p <= n:
		if prime[p] == 0:
			x += 1
			prime[p] = x
			for i in range(p * p, n + 1, p):
				if not prime[i]:
					prime[i] = x
		p += 1
	for p in range(2, n + 1):
		print(prime[p], end=' ')
n = int(input())
SieveOfEratosthenes(n)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	num = []
	for p in range(2, n + 1):
		if prime[p]:
			num.append(p)
	return num
primes = SieveOfEratosthenes(100009)
n = int(input())
ans = [0] * (n + 1)
ct = 1
for i in primes:
	if i <= n:
		ans[i] = ct
		ct += 1
for i in range(1, n + 1):
	if ans[i] == 0:
		for j in range(len(primes)):
			if not i % primes[j]:
				ans[i] = j + 1
				break
print(*ans[2:])


spf = [0] * 100001
for i in range(100001):
	spf[i] = i
spf[0] = 1
spf[1] = 1
for i in range(2, 100001):
	for j in range(i * i, 100001, i):
		spf[j] = min(i, spf[j])
ans = []
c = 0
n = int(input())
for i in range(2, n + 1):
	if spf[i] == i:
		c += 1
		ans.append(c)
	else:
		ans.append(ans[spf[i] - 2])
for i in ans:
	print(i, end=' ')


n = int(input())
a = [0] * (n - 1)
k = 1
for i in range(n - 1):
	if a[i] == 0:
		a[i] = k
		m = 2
		while True:
			if (i + 2) * m - 2 < n - 1:
				a[(i + 2) * m - 2] = k
			else:
				break
			m += 1
		k += 1
print(*a)


import sys, math, io, os, time, itertools, collections
mod = 10 ** 9 + 7
sys.setrecursionlimit(10000)
i = sys.stdin.readline
global start, end

def sieve(n):
	prime = [0 for k in range(n + 1)]
	p = 2
	color = 1
	while p <= n:
		if prime[p] == 0:
			prime[p] = color
			for k in range(p * p, n + 1, p):
				prime[k] = color
			color += 1
		p += 1
	return prime[2:]

def main():
	n = int(i())
	print(*sieve(n))
t = 1
start = time.perf_counter()
for _ in range(t):
	main()
end = time.perf_counter()


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
n = RI()
arr = [0] * (n + 1)
current = 1
for i in range(2, n + 1):
	if arr[i] == 0:
		for j in range(i, n + 1, i):
			arr[j] = current
		current += 1
print(*arr[2:])


from bisect import bisect_left
n = int(input())
a = [None] * (n - 1)
a[0] = 1
prime = [2]
for i in range(3, n + 1):
	flag = False
	i_sqrt = int(i ** 0.5)
	i2 = bisect_left(prime, i_sqrt)
	for (pi, p) in enumerate(prime[:i2 + 1]):
		if i % p == 0:
			flag = True
			break
	if flag:
		a[i - 2] = pi + 1
	else:
		a[i - 2] = len(prime) + 1
		prime.append(i)
print(*a)


def fastio():
	import sys
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
(n,) = I()
l = [0] * (n + 1)
k = 1
for i in range(2, n + 1):
	if l[i]:
		continue
	for j in range(i, n + 1, i):
		l[j] = k
	k += 1
print(*l[2:])


l = [2]
for i in range(3, 100000):
	for j in l:
		if j * j > i:
			l.append(i)
			break
		if i % j == 0:
			break
l.append(100003)
n = int(input())
k = [0 for i in range(n + 1)]
ind = 0
while l[ind] <= n:
	for i in range(0, n + 1, l[ind]):
		k[i] = ind + 1
	ind += 1
print(' '.join((str(x) for x in k[2:])))


n = int(input())

def computeGCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def is_prime(n):
	if n == 1:
		return False
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True
cur_max = 0
results = []
for i in range(2, n + 1):
	if is_prime(i):
		cur_max += 1
		results.append(cur_max)
	else:
		results.append(results[smallestDivisor(i) - 2])
print(*results)


import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def st():
	return input().rstrip('\n')

def val():
	return int(input())
n = val()
curr = 1
l = [None for i in range(n)]
for i in range(1, n):
	if not l[i]:
		for j in range(i, n, i + 1):
			if not l[j]:
				l[j] = curr
		curr += 1
print(*l[1:])


n = int(input())
l = [-1] * (n + 1)
used = False
num = 1
for i in range(2, n + 1):
	j = i
	while j < n + 1:
		if l[j] == -1:
			l[j] = num
			used = True
		j += i
	if used:
		used = False
		num += 1
l = l[2:]
print(*l)


n = int(input())
dados2 = []
for i in range(n + 1):
	dados2.append('-1')
numero_atual = 1
for i in range(2, n + 1):
	if dados2[i] == '-1':
		dados2[i] = str(numero_atual)
		multiplicador = 2
		while i * multiplicador <= n:
			dados2[i * multiplicador] = str(numero_atual)
			multiplicador += 1
		numero_atual += 1
print(' '.join(dados2[2:]))


def mindel(n):
	if n % 2 == 0:
		return 2
	d = 3
	while d * d <= n and n % d != 0:
		d += 2
	return d
n = int(input())
data = [1] * (n - 1)
isPrime = [1] * (n - 1)
i = 2
while i ** 2 <= n:
	if isPrime[i - 2]:
		j = i ** 2
		while j <= n:
			isPrime[j - 2] = 0
			j += i
	i += 1
curc = 1
for i in range(2, n + 1):
	if isPrime[i - 2]:
		data[i - 2] = curc
		curc += 1
	else:
		data[i - 2] = data[mindel(i) - 2]
for i in data:
	print(i, end=' ')


n = int(input().strip())
dp = [0] * (n + 1)
cur_factor = 2
color = 1
while cur_factor <= n:
	if not dp[cur_factor]:
		multiple = cur_factor
		while multiple <= n:
			if not dp[multiple]:
				dp[multiple] = color
			multiple += cur_factor
		color += 1
	cur_factor += 1
print(' '.join(map(str, dp[2:n + 1])))


n = int(input())
a_i = [0] * (n - 1)
asig = 0
for i in range(2, n + 1):
	if a_i[i - 2] == 0:
		asig += 1
		a_i[i - 2] = asig
		for j in range(i, n + 1, i):
			if a_i[j - 2] == 0 and j % i == 0:
				a_i[j - 2] = a_i[i - 2]
for i in range(0, n - 1):
	print(a_i[i])


import sys
from collections import defaultdict as dd
from itertools import permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
from heapq import heappush as hpush
from heapq import heappop as hpop
mod = 10 ** 9 + 7

def ri(flag=0):
	if flag == 0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())
n = ri(1)
check = [0 for i in range(n + 1)]
ans = 1
for i in range(2, n + 1):
	if check[i] == 0:
		for j in range(i, n + 1, i):
			check[j] = ans
		ans += 1
print(*check[2:])


n = int(input())
s = [0] * n
j = 1
while j < n:
	s[j] = 1
	j += 2
prime = [True] * n
p = 3
k = 2
while p * p <= n:
	if prime[p - 1] == True:
		if s[p - 1] != 1:
			s[p - 1] = k
			k += 1
		for i in range(p * 2, n + 1, p):
			prime[i - 1] = False
			if s[i - 1] != 1:
				s[i - 1] = k - 1
	p += 1
for i in range(1, n):
	if s[i] == 0:
		print(k, end=' ')
		k += 1
	else:
		print(s[i], end=' ')


n = int(input())
res = [0] * (n + 1)
cnt = 0
for i in range(2, n + 1):
	if res[i] == 0:
		j = i
		cnt += 1
		while j <= n:
			res[j] = cnt
			j += i
print(*res[2:])


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	ans = [0 for x in range(n + 1)]
	count = 0
	p = 2
	while p <= n:
		if prime[p] == True:
			ans[p] = count + 1
			count += 1
			for i in range(p * p, n + 1, p):
				prime[i] = False
				ans[i] = count
		p += 1
	for q in range(2, len(ans)):
		print(ans[q], end=' ')
SieveOfEratosthenes(int(input()))


n = int(input())
cont = 1
lista = [0] * (n - 1)
for i in range(2, n + 1):
	mudou = False
	for j in range(i, n + 1, i):
		if lista[j - 2] == 0:
			lista[j - 2] = cont
			mudou = True
	if mudou:
		cont += 1
for e in lista:
	print(e, end=' ')


n = int(input())
arr = [0 for x in range(n + 1)]
c = 1
for i in range(2, n + 1):
	flag = 0
	for j in range(i, n + 1, i):
		if arr[j] == 0:
			arr[j] = c
			flag = 1
	if flag:
		c += 1
for i in arr[2:]:
	print(i, end=' ')


N = int(input())

def prime_list(num):
	prime_table = [True for _ in range(num + 1)]
	i = 2
	while i ** 2 <= num:
		if prime_table[i]:
			j = i + i
			while j <= num:
				prime_table[j] = False
				j += i
		i += 1
	result = [i for i in range(num) if prime_table[i] and i >= 2]
	return result
ans = []
prime = prime_list(N + 1)

def check(num, dic):
	for p in prime:
		if num % p == 0:
			return dic[p]
p_set = set(prime)
r_prime = list(reversed(prime))
inc = 2
res = dict()
for i in range(2, N + 1):
	if i % 2 == 0:
		ans.append(1)
	elif i in p_set:
		ans.append(inc)
		res[i] = inc
		inc += 1
	else:
		ans.append(check(i, res))
for a in ans:
	print(a, end=' ')
print()


def mp():
	return map(int, input().split())

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def check():
	global n, a
	for i in range(2, n + 1):
		for j in range(2, n + 1):
			if gcd(i, j) == 1 and a[i] == a[j]:
				return False
	return True
n = int(input())
a = [10 ** 9] * (n + 1)
x = 1
d = 2
while d <= n:
	f = 0
	for i in range(d, n + 1, d):
		if x < a[i]:
			a[i] = x
			f = 1
	x += f
	d += 1
for i in range(2, n + 1):
	print(a[i], end=' ')


N = int(input())
ats = [0] * (N + 1)
piv = 1
for i in range(2, N + 1):
	dejau = False
	for j in range(i, N + 1, i):
		if ats[j] == 0:
			ats[j] = piv
			dejau = True
	if dejau:
		piv += 1
for i in range(2, N + 1):
	print(ats[i], end=' ')


import sys

def eratos(num):
	check = [0] * (num + 1)
	res = []
	cnt = 1
	for i in range(2, num + 1):
		if not check[i]:
			j = i
			while j <= num:
				check[j] = cnt
				j += i
			cnt += 1
	for i in range(2, num + 1):
		res.append(check[i])
	return res
n = int(sys.stdin.readline())
ans = eratos(n)
print(' '.join(map(str, ans)))


n = int(input())
res = [0] * (n + 1)
i = 2
m = 0
for i in range(2, n + 1, 1):
	if res[i] == 0:
		m += 1
		res[i] = m
		for j in range(i, n + 1, i):
			res[j] = res[i]
print(*res[2:])


import sys
from functools import reduce
from heapq import heappush, heappop, heapify
sys.setrecursionlimit(int(10000000.0))
R = lambda : map(int, input().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def main():
	(n,) = R()
	div = [0] * (n + 1)
	cnt = 1
	for i in range(2, n + 1):
		for j in range(i * i, n + 1, i):
			if div[j] == 0:
				div[j] = cnt
		if div[i] == 0:
			div[i] = cnt
			cnt += 1
	print(' '.join(map(str, div[2:])))
	return
while 1:
	try:
		main()
	except EOFError:
		break


n = int(input())
arr = [1] * (n + 1)
primes = []
is_prime = [True] * 100010
for i in range(2, 100010):
	if is_prime[i]:
		for j in range(2 * i, 100010, i):
			is_prime[j] = False
for i in range(2, 100010):
	if is_prime[i]:
		primes.append(i)
temp = 1
for i in range(2, n + 1, 1):
	if is_prime[i]:
		for j in range(i, n + 1, i):
			arr[j] = temp
		temp += 1
for i in range(2, len(arr)):
	print(arr[i], end=' ')
print()


n = int(input())
lis = [100000] * (n + 1)
i = j = 2
cur = 1
while i < n + 1:
	if lis[i] == 100000:
		while j < n + 1:
			lis[j] = min(cur, lis[j])
			j += i
		cur += 1
	i += 1
	j = i
print(*lis[2:])


n = int(input())
a = [0] * (n + 1)
tick = 1
for i in range(2, n + 1):
	if a[i] == 0:
		a[i] = tick
		for j in range(2 * i, n + 1, i):
			a[j] = tick
		tick += 1
print(*a[2:n + 1], sep=' ')


def sieve(n):
	a = [0] * (n + 1)
	cnt = 1
	for i in range(2, n + 1):
		if a[i] == 0:
			j = 0
			while j * i <= n:
				a[i * j] = cnt
				j += 1
			cnt += 1
	return a[2:]
print(*sieve(int(input())))


import sys
input = sys.stdin.readline
n = int(input())
sieve = [0] * (n + 1)
c = 1
for i in range(2, n + 1):
	if not sieve[i]:
		for j in range(i, n + 1, i):
			sieve[j] = c
		c += 1
for i in range(2, n + 1):
	print(sieve[i], end=' ')


def findsmaal(a):
	for i in range(2, int(a ** 0.5) + 1):
		if a % i == 0:
			return i
	return 0
n = int(input())
j = 2
A = [0 for i in range(1, n + 2)]
for i in range(2, n + 1):
	if i % 2 == 0:
		print(1, end=' ')
	else:
		a = findsmaal(i)
		if a == 0:
			print(j, end=' ')
			A[i] = j
			j += 1
		else:
			print(A[a], end=' ')


import sys
import os
from io import BytesIO, IOBase

def cel(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

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

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return defaultdict(int)

def ddl():
	return defaultdict(list)

def ddd():
	return defaultdict(defaultdict(int))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict
for _ in range(1):
	n = ii()
	res = [0 for i in range(n + 1)]
	num = 1
	p = 2
	while p <= n:
		if res[p] == 0:
			res[p] = num
			for i in range(2 * p, n + 1, p):
				res[i] = num
			num += 1
		p += 1
	print(*res[2:])


n = int(input())
arr = [i for i in range(2, n + 1)]
start = -1
ind = 0
while ind != len(arr):
	if arr[ind] < 0:
		ind += 1
		continue
	t = arr[ind]
	for x in range(ind, len(arr), t):
		arr[x] = start
	start -= 1
for x in range(len(arr)):
	arr[x] = -arr[x]
print(*arr)


def primen(n):
	for i in range(2, n):
		if n % i == 0:
			return i
n = int(input())
idxs = []
for i in range(n + 2):
	idxs.append(i + 1)
if n == 1:
	print(1)
	exit()
res = [0] * (n - 1)
prime = [True for i in range(100002)]
p = 2
arr = []
count = 0
while p * p <= 100002:
	if prime[p] == True:
		for i in range(p * p, 100002, p):
			prime[i] = False
	p += 1
for p in range(2, 100002):
	if prime[p]:
		arr.append(p)
nexti = arr[0]
together = dict(zip(arr, idxs))
for i in range(n - 1):
	if i + 2 == nexti:
		idx = together.get(i + 2)
		res[i] = idx
		count += 1
		if count >= len(arr):
			continue
		nexti = arr[count]
	else:
		no = primen(i + 2)
		idx = together.get(no)
		res[i] = idx
print(*res)


prime = []
res = {}

def Sieve(n):
	cnt = 0
	primes = {i: True for i in range(1, n + 1)}
	for i in range(2, n + 1):
		if primes[i]:
			cnt += 1
			res[i] = cnt
			for j in range(i * 2, n + 1, i):
				primes[j] = False
				res[j] = cnt
	primes[1] = False
	for i in range(1, n + 1):
		if primes[i]:
			prime.append(i)
N = int(input())
Sieve(N)
for i in range(2, N + 1):
	print(res[i], end=' ')
print()


def prost(i):
	for x in range(2, int(i ** 0.5 + 1)):
		if i % x == 0:
			return x
	return 1
l = 1
mass = []
for i in range(2, int(input()) + 1):
	if prost(i) == 1:
		mass.append(l)
		l += 1
	else:
		mass.append(mass[prost(i) - 2])
print(*mass)


from sys import stdin, stdout
from math import floor
st = lambda : list(stdin.readline().strip())
li = lambda : list(map(int, stdin.readline().split()))
mp = lambda : map(int, stdin.readline().split())
inp = lambda : int(stdin.readline())
pr = lambda n: stdout.write(str(n) + '\n')
mod = 1000000007

def solve():
	n = inp()
	dp = [-1 for i in range(n + 10)]
	i = 2
	val = 1
	while i <= n:
		if dp[i] == -1:
			dp[i] = val
			for j in range(2 * i, n + 1, i):
				dp[j] = val
			val += 1
		i += 1
	print(*dp[2:n + 1])
for _ in range(1):
	solve()


def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
n = int(input())
a = [0 for i in range(2, n + 1)]
prime = []
for i in range(n + 1):
	if isPrime(i):
		prime.append(i)

def process(i, r):
	for j in range(1, n // i + 1):
		if i * j - 2 <= n - 2:
			a[i * j - 2] = r
r = 1
for p in prime:
	process(p, r)
	r += 1
for r in a:
	print(r, end=' ')
print()


n = int(input())
t = 2
c = 1
ar = []

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n
while t <= n:
	if isPrime(t) == True:
		ar.append(c)
		c += 1
	else:
		l = smallestDivisor(t)
		ar.append(ar[l - 2])
	t += 1
print(*ar)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	vals = []
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			vals.append(p)
	return vals
n = int(input())
vals = SieveOfEratosthenes(n + 1)
x = [1 for i in range(n - 1)]
num = 1
for i in range(len(vals)):
	x[vals[i] - 2] = num
	for i in range(vals[i] * vals[i], n + 1, vals[i]):
		x[i - 2] = num
	num += 1
s = ''
for i in x:
	s += str(i) + ' '
print(s[:-1])


import math
n = int(input())
primes = {2: True}
for v in range(3, n + 1):
	a = 2
	b = False
	while a <= int(math.sqrt(v) + 1):
		if v % a == 0:
			b = True
			break
		a += 1
	if not b:
		primes[v] = True
ans = [0] * (n + 1)
for (i, p) in enumerate(primes):
	if p > n + 1:
		break
	for j in range(0, n + 1, p):
		if ans[j] == 0:
			ans[j] = i + 1
ans = ans[2:]
print(' '.join([str(v) for v in ans]))


check = []

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			check.append(p)
n = int(input())
prime = [True for i in range(n + 1)]
ans = [1 for i in range(n + 1)]
count = 1
p = 2
while p <= n:
	if prime[p] == True:
		ans[p] = count
		for i in range(p * p, n + 1, p):
			prime[i] = False
			ans[i] = count
		count += 1
	p += 1
for i in range(2, n + 1):
	print(ans[i], end=' ')


import os
import sys
from io import BytesIO, IOBase
import math

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(int(n))
	return l

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)
n = int(input())
ans = [-1] * (n + 1)
root = n ** 0.5
root = int(root)
ca = 0
for i in range(2, n + 1):
	if ans[i] == -1:
		ca = ca + 1
		ans[i] = ca
		for j in range(i, n + 1, i):
			ans[j] = ca
print(*ans[2:])


n = int(input())
a = [0] * (n + 1)
ca = 1
for i in range(2, n + 1):
	if a[i] != 0:
		continue
	m = 1
	while i * m <= n:
		a[i * m] = ca
		m += 1
	ca += 1
print(*a[2:n + 1])


n = int(input())
a = [-1] * (n - 1)
q = 0
for i in range(n - 1):
	if a[i] == -1:
		q += 1
		a[i] = q
		j = i + i + 2
		while j < n - 1:
			if a[j] == -1:
				a[j] = q
			j += i + 2
print(*a)


n = int(input())
bs = [0] * (n + 1)
next = 1
for p in range(2, n + 1):
	if bs[p] == 0:
		for q in range(p, n + 1, p):
			if bs[q] == 0:
				bs[q] = next
		next += 1
print(' '.join(map(str, bs[2:])))


def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def oddfact(n):
	x = int(n ** 0.5)
	for i in range(3, x + 1, 2):
		if n % i == 0:
			return i
			break
n = int(input())
a = [1] * (n + 1)
j = 2
for i in range(3, n + 1, 2):
	if isPrime(i):
		a[i] = j
		j = j + 1
	else:
		val = oddfact(i)
		a[i] = a[val]
for i in range(2, n + 1):
	print(a[i], end=' ')
print('')


n = int(input())
t = [0] * (10 ** 5 + 1)
z = 1
wyn = ''
for x in range(2, n + 1, +1):
	if t[x] == 0:
		for h in range(x, n + 1, +x):
			t[h] = z
		z += 1
	wyn += str(t[x]) + ' '
print(wyn.rstrip(' '))


n = int(input())
s = set()
r = [0] * (n + 1)
color = 1
a = 2
while len(s) < n - 1:
	for i in range(a, n + 1):
		if r[i] == 0:
			a = i
			break
	t = a
	while t < n + 1:
		if r[t] == 0:
			r[t] = color
			s.add(t)
		t += a
	color += 1
[print(i, end=' ') for i in r[2:]]


import math

def main():
	n = int(input())
	d = [0, 0, 1, 2]
	m = 2
	for i in range(4, n + 1):
		f = False
		for j in range(2, int(math.sqrt(i)) + 1):
			if i % j == 0:
				d.append(d[j])
				f = True
				break
		if f is False:
			m += 1
			d.append(m)
	for di in d[2:n + 1]:
		print(di, end=' ')
main()


n = int(input())
s = [0 for _ in range(n)]
m = 1
for i in range(1, n):
	if s[i] == 0:
		s[i] = m
		for j in range(i, n, i + 1):
			s[j] = m
		m += 1
for i in range(1, n):
	print(s[i], end=' ')


n = int(input())
least_prime = [0] * (n + 1)
least_prime[1] = 1
cnt = 1
for i in range(2, n + 1):
	if least_prime[i] == 0:
		least_prime[i] = cnt
		for j in range(i * i, n + 1, i):
			if least_prime[j] == 0:
				least_prime[j] = cnt
		cnt += 1
print(*least_prime[2:])


import sys

def prime_sieve(n):
	flag = n % 6 == 2
	sieve = bytearray((n // 3 + flag >> 3) + 1)
	for i in range(1, int(n ** 0.5) // 3 + 1):
		if not sieve[i >> 3] >> (i & 7) & 1:
			k = 3 * i + 1 | 1
			for j in range(k * k // 3, n // 3 + flag, 2 * k):
				sieve[j >> 3] |= 1 << (j & 7)
			for j in range(k * (k - 2 * (i & 1) + 4) // 3, n // 3 + flag, 2 * k):
				sieve[j >> 3] |= 1 << (j & 7)
	return sieve

def prime_list(n):
	res = []
	if n > 1:
		res.append(2)
	if n > 2:
		res.append(3)
	if n > 4:
		sieve = prime_sieve(n + 1)
		res.extend((3 * i + 1 | 1 for i in range(1, (n + 1) // 3 + (n % 6 == 1)) if not sieve[i >> 3] >> (i & 7) & 1))
	return res

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
n = int(input())
myArr = prime_list(n)
Ans = [0] * (n + 1)
z = 1
for i in myArr:
	Ans[i] = z
	z += 1
for i in range(2, n + 1):
	for j in range(i, n + 1, i):
		if Ans[j] == 0:
			Ans[j] = Ans[i]
		else:
			Ans[j] = min(Ans[j], Ans[i])
Ans = Ans[2:]
print(*Ans, sep=' ')


import sys
input = sys.stdin.readline
from collections import defaultdict as dc
from collections import Counter
from bisect import bisect_right, bisect_left
import math
from heapq import heapify, heappop, heappush
n = int(input())
l = [1] * (n + 1)
f = [0] * (n + 1)
p = 2
c = 1
while p < n + 1:
	if f[p] == 0:
		f[p] = 1
		l[p] = c
		for i in range(2 * p, n + 1, p):
			f[i] = 1
			l[i] = c
		c += 1
	p += 1
print(*l[2:])


sz = int(input())
arr = [0] * (sz + 1)
pms = [2]
setval = 2
for i in range(2, sz + 1, 2):
	arr[i] = 1
for j in range(3, sz + 1):
	if arr[j] == 0:
		for u in range(j, sz + 1, j):
			arr[u] = setval
		setval += 1
for k in range(2, sz + 1):
	print(arr[k], end=' ')


def gns():
	return [int(x) for x in input().split()]
n = int(input())
ns = [None] * (n + 1)

def sift(x, cl):
	i = x
	while i <= n:
		ns[i] = cl
		i += x
i = 2
cl = 1
while i <= n:
	while i <= n and ns[i] != None:
		i += 1
	if i > n:
		break
	sift(i, cl)
	i += 1
	cl += 1
for i in range(2, n):
	print(ns[i], end=' ')
print(ns[-1])


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 1000000007

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def primeN(n):
	prime = [True for i in range(n + 1)]
	prime[0] = False
	p = 2
	c = 1
	while p * p <= n:
		if prime[p]:
			ans[p] = c
			for i in range(p * p, n + 1, p):
				prime[i] = False
				ans[i] = c
			c += 1
		p += 1
	return [p for p in range(n + 1) if prime[p]]
n = Int()
ans = [0] * (n + 1)
primeN(n)
c = max(ans) + 1
for i in range(2, n + 1):
	if ans[i] == 0:
		ans[i] = c
		c += 1
print(*ans[2:])


import sys

def input():
	return sys.stdin.readline().strip()

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def prime_sieve(n):
	flag = n % 6 == 2
	sieve = bytearray((n // 3 + flag >> 3) + 1)
	for i in range(1, int(n ** 0.5) // 3 + 1):
		if not sieve[i >> 3] >> (i & 7) & 1:
			k = 3 * i + 1 | 1
			for j in range(k * k // 3, n // 3 + flag, 2 * k):
				sieve[j >> 3] |= 1 << (j & 7)
			for j in range(k * (k - 2 * (i & 1) + 4) // 3, n // 3 + flag, 2 * k):
				sieve[j >> 3] |= 1 << (j & 7)
	return sieve

def prime_list(n):
	res = []
	if n > 1:
		res.append(2)
	if n > 2:
		res.append(3)
	if n > 4:
		sieve = prime_sieve(n + 1)
		res.extend((3 * i + 1 | 1 for i in range(1, (n + 1) // 3 + (n % 6 == 1)) if not sieve[i >> 3] >> (i & 7) & 1))
	return res
N = int(input())
ans = [0] * (N + 1)
m = 1
prime = prime_list(N)
for i in prime:
	ans[i] = m
	m += 1
for i in range(2, N + 1):
	for j in range(i, N + 1, i):
		if ans[j] == 0:
			ans[j] = ans[i]
		else:
			ans[j] = min(ans[j], ans[i])
ans = ans[2:]
print(*ans)


n = int(input())
ans = [0] * (n + 1)
count = 0
for i in range(2, n + 1):
	if ans[i] == 0:
		count += 1
		ans[i] = count
		for j in range(i, n + 1, i):
			ans[j] = ans[i]
ans.pop(0)
ans.pop(0)
print(*ans)


a = int(input())
n = 2
f = 1
arr = []

def prime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def smallestFactor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n
while n <= a:
	if prime(n) == True:
		arr.append(f)
		f += 1
	else:
		u = smallestFactor(n)
		arr.append(arr[u - 2])
	n += 1
print(*arr)


def compute(n):
	val = 1
	primes = [True for i in range(n + 1)]
	primes[0] = False
	primes[1] = False
	fs = [0 for i in range(n + 1)]
	p = 2
	fs[2] = 1
	while p <= int(n ** 0.5):
		cur = p
		cur = cur + p
		while cur <= n:
			primes[cur] = False
			if fs[cur] == 0:
				fs[cur] = val
			cur = cur + p
		p = p + 1
		while not primes[p]:
			p = p + 1
		val = val + 1
		fs[p] = val
	for i in range(int(n ** 0.5) + 1, n + 1):
		if primes[i]:
			fs[i] = val
			val = val + 1
	return fs

def main():
	n = int(input())
	fs = compute(n)
	st = ''
	for i in range(2, n + 1):
		st = st + str(fs[i]) + ' '
	print(st)
main()


import math

def is_prime(n):
	if n % 2 == 0:
		return n == 2
	d = 3
	while d * d <= n and n % d != 0:
		d += 2
	return d * d > n
n = int(input())
a = []
d = {}
pr = 2
for i in range(2, n + 1):
	if i % 2 == 0:
		a.append(1)
	elif is_prime(i):
		a.append(pr)
		d[i] = pr
		pr += 1
	else:
		for j in range(2, int(math.sqrt(i)) + 1):
			if i % j == 0:
				a.append(d[j])
				break
print(*a)


s = int(input())
l = ['a' for x in range(s + 1)]
p = 2
c = 1
while p * p <= s:
	if l[p] == 'a':
		l[p] = c
		for i in range(p * p, s + 1, p):
			l[i] = c
		c += 1
	p += 1
for i in range(2, len(l)):
	if l[i] == 'a':
		l[i] = c
		c += 1
for i in l[2:]:
	print(i, end=' ')


n = int(input())
is_prime = [True] * (n - 1)
a = [0] * (n - 1)
k = 1
for i in range(2, n + 1):
	if is_prime[i - 2]:
		a[i - 2] = k
		for j in range(i * i, n + 1, i):
			is_prime[j - 2] = False
			a[j - 2] = k
		k += 1
print(' '.join(map(str, a)))


n = int(input())
primes = []
check_list = [0 for x in range(10 ** 5 + 100)]
num = 1
for x in range(2, 10 ** 5):
	if check_list[x] != 0:
		continue
	counter = x
	while True:
		if check_list[counter] == 0:
			check_list[counter] = num
		counter += x
		if counter > 10 ** 5 + 10:
			break
	num += 1
for x in range(2, n + 1):
	print(check_list[x], end=' ')


primes = []
primesize = 10 ** 5 + 1
notprime = [0 for i in range(0, primesize + 1)]
notprime[0] = notprime[1] = 1
marker = 1
for i in range(2, primesize + 1):
	if notprime[i] == 0:
		notprime[i] = marker
		primes.append(i)
		for j in range(i + i, primesize + 1, i):
			notprime[j] = marker
		marker += 1
n = int(input())
for i in range(2, n + 1):
	print(notprime[i], end=' ')


import math
N = int(input())
P = [2]
for k in range(3, N + 1):
	f = 1
	for l in range(2, int(math.sqrt(k)) + 1):
		if k % l == 0:
			f = 0
			break
	if f == 1:
		P.append(k)
a = [0 for k in range(N + 1)]
t = 0
for p in P:
	t += 1
	s = 0
	while (s + 1) * p <= N:
		s += 1
		if a[s * p] == 0:
			a[s * p] = t
print(*a[2:N + 1], sep=' ')


n = int(input())
vis = [0 for i in range(n + 1)]
cur = 1
for i in range(2, n + 1):
	if vis[i] == 0:
		for j in range(i, n + 1, i):
			vis[j] = cur
		cur += 1
for i in range(2, n + 1):
	print(vis[i], end=' ')


n = int(input())
bitmap = [0] * (n + 1)
colour = 1
for i in range(2, n + 1):
	if not bitmap[i]:
		for k in range(1, n // i + 1):
			bitmap[i * k] = colour
		colour += 1
print(*bitmap[2:])


def solver(n):
	arr = [-1 for i in range(n + 1)]
	p = 2
	k = 1
	flag = True
	while p < n + 1:
		for i in range(p, n + 1, p):
			if arr[i] == -1:
				flag = False
				arr[i] = k
		if flag == False:
			flag = True
			k = k + 1
		p += 1
	return arr
n = int(input())
ans = solver(n)
print(*ans[2:])


n = int(input())
if n == 2:
	print(1)
elif n == 3:
	print(1, 2)
else:
	L = [True] * (n + 1)
	L[0] = 0
	L[1] = 0
	i = 2
	temp = 1
	while i * i <= n:
		if L[i] is True:
			L[i] = temp
			temp += 1
			x = i * i
			while x <= n:
				L[x] = L[i]
				x += i
		i += 1
	counter = 1
	x = 1
	m = 1
	for i in range(2, n + 1):
		if L[i] is True:
			print(m + 1, end=' ')
			m += 1
		else:
			print(L[i], end=' ')
			m = max(m, L[i])