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.*; 
import javafx.util.Pair; 

public class taskC_june3 
{ 

/*
 *   ********   *******    ******** 	
 *   *          *    *           *
 *   *          *   *           * 
 *   *          * *            *
 *   *          *   *         *
 *   ********   *    *       *
 */
	static	Reader in=new Reader();
	static Scanner sc=new Scanner(System.in);
	
	static Vector<Integer> hlist=new Vector<Integer>();
	static  void prime(int n) 
	    { 
	        boolean prime[] = new boolean[n+1]; 
	        for(int i=0;i<=n;i++) 
	            prime[i] = true; 
	          
	        for(int p = 2; p*p <=n; p++) 
	        { 
	            // If prime[p] is not changed, then it is a prime 
	            if(prime[p] == true) 
	            { 
	                // Update all multiples of p 
	                for(int i = p*p; i <= n; i += p) 
	                    prime[i] = false; 
	            } 
	        } 
	          
	        // Print all prime numbers 
	        for(int i = 2; i <= n; i++) 
	        { 
	            if(prime[i] == true) 
	                hlist.add(i);
	        } 
	    } 

	public static void main(String[] args) throws IOException 
	{ 
		int n=in.integer();
		prime(n);
		int arr[]=new int[n+1];
		int count=1;
		Arrays.fill(arr,0);
		Collections.sort(hlist);
		for(int i=0;i<hlist.size();i++) {
			int data=hlist.get(i);
			int j=2;
			int x=data;
			while(x<=n) {
				if(arr[x]==0)
					arr[x]=count;
				//System.out.println(arr[x]+" "+x);
				x=data*j;
				j++;
			}
			count++;
		}
	for(int i=2;i<=n;i++)
		System.out.print(arr[i]+" ");
	}

 static int partition(Pair<Integer,Integer> arr[], int low, int high) 
    { 
        int pivot = arr[high].getKey();  
        int i = (low-1);
        for (int j=low; j<high; j++) 
        {  
            if (arr[j].getKey() <= pivot) 
            { 
                i++;
                Pair<Integer,Integer> temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
            } 
        }
        Pair<Integer,Integer> temp = arr[i+1]; 
        arr[i+1] = arr[high]; 
        arr[high] = temp; 
  
        return i+1; 
    } 
   static void sort(Pair<Integer,Integer> arr[], int low, int high) 
    { 
        if (low < high) 
        { 
            int pi = partition(arr, low, high); 
            sort(arr, low, pi-1); 
            sort(arr, pi+1, high); 
        } 
    }
	/*
	 * seach algorithm
	 */
	static int return_greater_index(int arr[],int start,int end,int x)
	{
		int ans=-1;
		int mid;
		while(start<=end) {
			 mid=(start+end)/2;
			if(arr[mid]<=x)
				start=mid+1;
			else 
				{
				ans=mid;
				end=mid-1;
				}
		}
		return ans;
	}
public static int lowerBound(int[] a, int v)
	{
		int low = -1, high = a.length;
		while(high-low > 1){
			int h = high+low>>>1;
			if(a[h] >= v){
				high = h;
			}else{
				low = h;
			}
		}
		return high;
	}
static int return_lower_index(int arr[],int start,int end,int x)
	{
		int ans=-1;
		int mid;
		while(start<=end) {
			 mid=(start+end)/2;
			if(arr[mid]<=x) {
				ans=mid;
				start=mid+1;
			}
			else 
				{
				end=mid-1;
				}
		}
		return ans;
	}
	/*
	 * pairs of <int,int> <double,double>
	 */
	static Pair<Integer,Integer> pair(int x,int y){
		Pair<Integer,Integer> p=new Pair<Integer, Integer>(x,y);
		return p;
	}
	static Pair<Double,Double> pair(double x,double y){
		Pair<Double,Double> p=new Pair<Double,Double>(x,y);
		return p;
	}
	/*
	 * for loop
	 */
static void rep(int arr[]) throws IOException {
	int n=arr.length;
	for(int i=0;i<n;i++)
		arr[i]=in.integer();
}
	/*display 
	 array
	 */
	static void display(int arr[][],int x,int y) {
		for(int i=0;i<x;i++) {
			for(int j=0;j<y;j++)
			{
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
	}
	static void display(int arr[]) {
		int x=arr.length;
			for(int j=0;j<x;j++)
			{
				System.out.print(arr[j]+" ");
			}
			System.out.println();
	}
	
	/*
	 * input 
	 */
	
	static class Reader 
	{ 
		final private int BUFFER_SIZE = 1 << 16; 
		private DataInputStream din; 
		private byte[] buffer; 
		private int bufferPointer, bytesRead; 

		public Reader() 
		{ 
			din = new DataInputStream(System.in); 
			buffer = new byte[BUFFER_SIZE]; 
			bufferPointer = bytesRead = 0; 
		} 

		public Reader(String file_name) throws IOException 
		{ 
			din = new DataInputStream(new FileInputStream(file_name)); 
			buffer = new byte[BUFFER_SIZE]; 
			bufferPointer = bytesRead = 0; 
		} 

		public String string() throws IOException 
		{ 
			byte[] buf = new byte[64]; // line length 
			int cnt = 0, c; 
			while ((c = read()) != -1) 
			{ 
				if (c == '\n') 
					break; 
				buf[cnt++] = (byte) c; 
			} 
			return new String(buf, 0, cnt); 
		} 

		public int integer() throws IOException 
		{ 
			int ret = 0; 
			byte c = read(); 
			while (c <= ' ') 
				c = read(); 
			boolean neg = (c == '-'); 
			if (neg) 
				c = read(); 
			do
			{ 
				ret = ret * 10 + c - '0'; 
			} while ((c = read()) >= '0' && c <= '9'); 

			if (neg) 
				return -ret; 
			return ret; 
		} 

		public long _long() throws IOException 
		{ 
			long ret = 0; 
			byte c = read(); 
			while (c <= ' ') 
				c = read(); 
			boolean neg = (c == '-'); 
			if (neg) 
				c = read(); 
			do { 
				ret = ret * 10 + c - '0'; 
			} 
			while ((c = read()) >= '0' && c <= '9'); 
			if (neg) 
				return -ret; 
			return ret; 
		} 

		public double _double() throws IOException 
		{ 
			double ret = 0, div = 1; 
			byte c = read(); 
			while (c <= ' ') 
				c = read(); 
			boolean neg = (c == '-'); 
			if (neg) 
				c = read(); 

			do { 
				ret = ret * 10 + c - '0'; 
			} 
			while ((c = read()) >= '0' && c <= '9'); 

			if (c == '.') 
			{ 
				while ((c = read()) >= '0' && c <= '9') 
				{ 
					ret += (c - '0') / (div *= 10); 
				} 
			} 

			if (neg) 
				return -ret; 
			return ret; 
		} 

		private void fillBuffer() throws IOException 
		{ 
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
			if (bytesRead == -1) 
				buffer[0] = -1; 
		} 

		private byte read() throws IOException 
		{ 
			if (bufferPointer == bytesRead) 
				fillBuffer(); 
			return buffer[bufferPointer++]; 
		} 

		public void close() throws IOException 
		{ 
			if (din == null) 
				return; 
			din.close(); 
		} 
	} 

}