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

Solution:
from collections import Counter as D, defaultdict as dd
from math import factorial as ft, ceil as aron, log
from fractions import gcd as pg 
from bisect import insort as ins, bisect_left as bl, bisect_right as br
import sys

#sys.stdin=open("./testfile1.py","r")
raw_input=sys.stdin.readline

f1=lambda : map(int,raw_input().split())
f2=lambda : map(int,list(raw_input()))
f3=lambda : int(raw_input())
f4=lambda : raw_input().rstrip()


def SieveOfEratosthenes(n): 
    

    prime = [None]*(n+1) 
    p = 2
    data=0
    k=0
    np=0
    while (k<n-1): 
          
        # If prime[p] is not changed, then it is a prime 
        if (prime[p] == None): 
            data=data+1    
            np+=1
            # Update all multiples of p 
            for i in xrange(p, n+1, p):
            	if prime[i]!=None: k-=1 
                prime[i] =  data
                k=k+1
        p += 1
 
    # Print all prime numbers 
    for p in xrange(2, n+1):
            if prime[p]==None:
                np=np+1
                prime[p]=np
    print " ".join(map(str,prime[2:]))

def main():
	
	s=f3()
	SieveOfEratosthenes(s)
	
	


if __name__ == '__main__':
	main()