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.awt.Point;
import java.math.*;
import java.io.*;
@SuppressWarnings("unused")
public class Codeforces {int[] b;	String g="";int c=0;int modu=1000000000+7;ArrayList<Integer> list=new ArrayList<Integer>();String s;int[] size;int[] id;
int[]ab;int[] data;int mod=100000;LinkedList<Integer> queue=new LinkedList<Integer>();int dis=0;int max=0;ArrayList<Integer>[] arr;static int MAX = 1000001; 
static int factor[];long glo;int f;int gl;int[] rem;int[] vis;int[] a;int n;int k;
int[] rank;int[] par;long[] facto;
	public static void main(String[] args)  {
                new Codeforces().solve();
                                  }
	
            public void solve(){
            	
            	int n=sc.nextInt();
            	
            	int[] a=new int[n+1];int c=0,k=1;int g=0;
            	
            	  for(int p = 2; p <=n; p++) 
                  { 
            		  if(g==n-1)
            			  break;
            		  if(a[p]!=0) {
            			  continue;
            		  }
                      for(int i=p;i<=n;i+=p) {
                    	  if(a[i]!=0)
                    		  continue;
                    	  a[i]=k;
                    	  g++;
                    	  if(g==n-1)
                    		  break;
                      }
                     k++;
            	
                  }
            	  for(int i=2;i<=n;i++) {
            		  System.out.print(a[i]+" ");
            	  }
                }
           
          void factorial() {
        	  facto[0]=1;
        	  for(int i=1;i<=1000;i++) {
        		  facto[i]=(facto[i-1]%modu*i%modu)%modu;
        	  }
          }
           
           
            public class Node{
        		int x;long color;int y;
        		Node par;
        		public Node(int a,int b) {
        			x=a;y=b;
        			
        		}
        	}
       				
       				 FastReader sc=new FastReader();
       				 static class FastReader
       				     {
       				         BufferedReader br;
       				         StringTokenizer st;
       				  
       				         public FastReader()
       				         {
       				             br = new BufferedReader(new
       				                      InputStreamReader(System.in));
       				         }
       				  
       				         String next()
       				         {
       				             while (st == null || !st.hasMoreElements())
       				             {
       				                 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());
       				         }
       				  
       				         double nextDouble()
       				         {
       				             return Double.parseDouble(next());
       				         }
       				  
       				         String nextLine()
       				         {
       				             String str = "";
       				             try
       				             {
       				                 str = br.readLine();
       				             }
       				             catch (IOException e)
       				             {
       				                 e.printStackTrace();
       				             }
       				             return str;
       				         }
       				     }}