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

Solution:
import java.util.*;
import java.io.*;
public class Main
{
	
	static long gcd(long a, long b) {
		if(b==0)
			return a;
		else
			return gcd(b, a%b);
	}
	
	static boolean isPrime(int n) { 
		if(n==2)
			return true;
		if(n%2==0)
			return false;
        for (int i = 3; i <= Math.sqrt(n); i+=2) 
            if (n % i == 0) 
                return false; 
  
        return true; 
    } 
	
	static int[] primeGenerator() {
		int arr[] = new int[10000], length=0;
		for(int i=2; i<10000; i++) {
			if(isPrime(i))
				arr[length++]=i;	
		}
		return Arrays.copyOfRange(arr, 0, length);
	}
	
	 public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
		int num = sc.nextInt();
		int arr[] = new int[num-1], arr1[]=primeGenerator(), position=1;
	    for(int i=2; i<=num; i++) {
	    	if(isPrime(i))
	    		arr[i-2]=position++;
	    	else {
	    		if(i%2==0)
	    			arr[i-2]=1;
	    		else {
	    			for (int j = 3; j <= Math.sqrt(i); j+=2) 
	    	            if (i % j == 0) {
	    	            	arr[i-2]=Arrays.binarySearch(arr1, j)+1;
	    	            	break;
	    	            }
	    		}
	    	}
	    }
	    for(int i=0; i<num-1; i++)
	    	out.print(arr[i]+" ");
        out.flush();
    }
}