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$.

Difficulty: interview

Starter code:

Solutions:
def isPrime(n):
	# a prime(except 2 or 3) is of the form 6k-1 or 6k+1
	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, .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:])

def SieveOfEratosthenes(n,ans):
    c=1
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
          
        # If prime[p] is not changed, then it is a prime 
        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:]))

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:])


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:])))            


#Bhargey Mehta (Sophomore)
#DA-IICT, Gandhinagar
import sys, math, queue, bisect
#sys.stdin = open("input.txt", "r")
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:])

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 = [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())


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 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 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)

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())
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]))




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()


def __starting_point():
    main()

__starting_point()

n = int(input())
l = [0]*(n+1)

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


# import math

# for i in range(2, n+1):
# 	for j in range(i, n+1):
# 		if math.gcd(i, j) == 1:
# 			print(i, j)
# 			print(l[i] != l[j])


#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

def __starting_point():
    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:])))

__starting_point()

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())

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:])))


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()

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()


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:]))



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

def __starting_point():
    main()

__starting_point()



def __starting_point():
    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])))

__starting_point()

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()

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()

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=' ')