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.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
 
public class oK{
		    void pre() throws Exception{}
		    void solve(int TC) throws Exception{
		    	int n=ni();
		   Integer a[]=new Integer[n+2];
		  
		   for(int i=0;i<n;i++) {
			   a[i]=i+2;
			
		   }
		   int flag=1;
		 int b[]=new int[n+1];
		
		 int x=0;
		 for(int j=2;j<n+1;j++) {
		 	if(flag==1)x++;
		 	flag=0;
		 	int y=j;
			 for(int i=y;i<n+1;i=i+j) {
				
			if(b[i]==0) {
				flag=1;
				 b[i]=x; 
			}
			 }
		   
		 }
		 for(int j=2;j<n+1;j++) {
		 p(b[j] + " ");
		    }
		    }
		        
		    

static int gcd(int a, int b) 
{ 
  if (b == 0) 
    return a; 
  return gcd(b, a % b);  
} 
  
		    		
		    		
		    		
		    
		    
		    
		    
		    
		   // void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
		    static boolean multipleTC = false, memory = false;
		    FastReader in;PrintWriter out;
		    void run() throws Exception{
		        in = new FastReader();
		        out = new PrintWriter(System.out);
		        int T = (multipleTC)?ni():1;
		        pre();for(int t = 1; t<= T; t++)solve(t);
		        out.flush();
		        out.close();
		    }
		    public static void main(String[] args) throws Exception{
		        if(memory)new Thread(null, new Runnable() {public void run(){try{new oK().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
		        else new oK().run();
		    }
		    void p(Object o){out.print(o);}
		    void pn(Object o){out.println(o);}
		    void pni(Object o){out.println(o);out.flush();}
		    String n()throws Exception{return in.next();}
		    String nln()throws Exception{return in.nextLine();}
		    int ni()throws Exception{return Integer.parseInt(in.next());}
		    long nl()throws Exception{return Long.parseLong(in.next());}
		
		    class FastReader{
		        BufferedReader br;
		        StringTokenizer st;
		        public FastReader(){
		            br = new BufferedReader(new InputStreamReader(System.in));
		        }
		
		        public FastReader(String s) throws Exception{
		            br = new BufferedReader(new FileReader(s));
		        }
		
		        String next() throws Exception{
		            while (st == null || !st.hasMoreElements()){
		                try{
		                    st = new StringTokenizer(br.readLine());
		                }catch (IOException  e){
		                    throw new Exception(e.toString());
		                }
		            }
		            return st.nextToken();
		        }
		
		        String nextLine() throws Exception{
		            String str = "";
		            try{   
		                str = br.readLine();
		            }catch (IOException e){
		                throw new Exception(e.toString());
		            }  
		            return str;
		        }
		    }
		}