Problem: 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 ≠ 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](https://en.wikipedia.org/wiki/Coprime_integers) if their [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) is 1.

Input

The only line contains the integer n (2 ≤ n ≤ 10^5).

Output

Print n-1 integers, a_2, a_3, …, a_n (1 ≤ a_i ≤ 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 ≠ 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.

Solution (in PYTHON3):

Solution:
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):
    # print(sp[i])
    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:])