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:
from sys import stdin, setrecursionlimit, stdout
setrecursionlimit(100) #use "python" instead of "pypy" to avoid MLE
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']


#######################################################################################
###########################    M Y     F U N C T I O N S    ###########################
#######################################################################################

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



#######################################################################################
###########################    M A I N     P R O G R A M    ###########################
#######################################################################################



test=test_case=1
#test_case=ii()
while test<=test_case:
    test+=1


    print(*sieve(ii()))