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.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) {
        FastReader fs=new FastReader();
        PrintWriter out=new PrintWriter(System.out);
        int t=1;
        //t=fs.nextInt();
        for(int i=1;i<=t;i++) {
        	Main m=new Main();
            m.solve(i,out,fs);
        }
        out.close();
    } 
   

    public void solve(int test,PrintWriter out,FastReader fs){
        int n=fs.nextInt();
        int ans[]=new int[n+1];
        int count=1;
        for(int i=2;i<=n;i++){
            boolean prime=true;
            for(int j=2;j<=Math.sqrt(i);j++){
                if(i%j==0){
                    ans[i]=ans[j];
                    prime=false;
                }
            }
            if(prime){
                ans[i]=count++;
            }
        }
        for(int i=2;i<=n;i++){
            out.print(ans[i]+" ");
        }
    }
}
class SegmentTree{
	long t[];
	SegmentTree(int n){
		t=new long[4*n];
	}
	void update(int v,int tl,int tr,int pos,long delta) {
		if(tl==tr) {
			t[v]+=delta;
		}else {
			int tm=(tl+tr)/2;
			if(pos<=tm)
				update(2*v,tl,tm,pos,delta);
			else
				update(2*v+1,tm+1,tr,pos,delta);
			t[v]=t[2*v]+t[2*v+1];
		}
	}
	long sum(int v,int l,int r,int tl,int tr) {
		if(l>r)return 0;
		if(l==tl&&r==tr) {
			return t[v];
		}else {
			int tm=(tl+tr)/2;
			return sum(2*v,l,Integer.min(r,tm),tl,tm)+sum(2*v+1,Integer.max(l, tm+1),r,tm+1,tr);
		}
	}
}
class FastReader{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st=new StringTokenizer("");  
    String next(){
        while(!st.hasMoreTokens()){
            try {
                st=new StringTokenizer(br.readLine()); 
            } catch (IOException e) {
				e.printStackTrace();
			}
        }
        return st.nextToken();
    }
    int nextInt(){
        return Integer.parseInt(next());
    }
    long nextLong(){
        return Long.parseLong(next());
    }
    int[] nextIntArray(int n){
        int a[]=new int[n];
        for(int i=0;i<n;i++)a[i]=nextInt();
        return a;
    } 
    long[] nextLongArray(int n){
        long a[]=new long[n];
        for(int i=0;i<n;i++)a[i]=nextInt();
        return a;
    }
    char[] nextCharArray(){
        char a[]=next().toCharArray();
        return a;
    }
}