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:
//package graphs;
import java.util.*;
public class PW {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s=new Scanner(System.in);
		
		//int a=s.nextInt();
		//lon n=s.nextLong();
		int n=s.nextInt();
		int ans[]=new int[n+1];
		
		int count=1;
		for(int i=2;i<=n;i++)
		{
			
			if(prime(i))
			{
				ans[i]=count;
				for(int j=i;(long)i*(long)j<=n;j++)
				{
					ans[i*j]=count;
				}
				count++;
			}
			System.out.print(ans[i]+" ");
		}
		
		
		
		
		
	}
	
	
	
	public static long solve(int n, int r)
    {


        long p = 1, k = 1;
        if (n - r < r) {
            r = n - r;
        }
 
        if (r != 0) {
            while (r > 0) {
                p *= n;
                k *= r;
 
                long m = __gcd(p, k);
 
                
                p /= m;
                k /= m;
 
                n--;
                r--;
            }
 
           
        }
        else {
            p = 1;
        }
 
        
        //System.out.println(p);
        return p;
    }
	
	public static long __gcd(long n1, long n2)
    {
        long gcd = 1;
 
        for (int i = 1; i <= n1 && i <= n2; ++i) {
            // Checks if i is factor of both integers
            if (n1 % i == 0 && n2 % i == 0) {
                gcd = i;
            }
        }
        return gcd;
    }
	
	public static boolean prime(int n)
	{
		if(n<=2)
			return true;
		
		for(int i=2;i<=Math.sqrt(n);i++)
		{
			if(n%i==0)
				return false;
		}
		
		return true;
		
	}
}