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 Fight {
	static Scanner sc=new Scanner(System.in);
	static PrintWriter out=new PrintWriter(System.out);
	static ArrayList<Integer>[] adj;
	static boolean[] vis;
	public static boolean a[];
	static int max;
	static int c[];
	public static void main(String[] args) throws IOException {	
		int n=sc.nextInt();
		sieve(n);
		
			}
	static int[] com;
	static int[] begin;
	static int x;
	  static int [] end;
	static int cost=Integer.MAX_VALUE;
	static HashSet<Integer> set;
	static void dfs(int u) {
			vis[u] = true;
			com[x]=u;
			begin[u]=x;
			x++;
			
			for (int v : adj[u]) {
	    		if (!vis[v]) {
	    			dfs(v);	
	    		}
	    		
	    	}
			end[u]=x-1;
	    	
	    }
		
		
	
	static HashSet<Integer> primes;
	static int[] isComposite;

	static void sieve(int N)	// O(N log log N) 
	{
		isComposite = new int[N+1];					
		isComposite[0] = isComposite[1] = 1;			// 0 indicates a prime number
		primes = new HashSet<Integer>();
		int curmax=0;
		int ans[]=new int[N+1];

		for (int i = 2; i <= N; ++i) 					//can loop till i*i <= N if primes array is not needed O(N log log sqrt(N)) 
			if (isComposite[i] == 0) 					//can loop in 2 and odd integers for slightly better performance
			{
				x++;
				ans[i]=x;
				primes.add(i);
				if(1l * i * i <= N)
					for (int j = i * i; j <= N; j += i) {	// j = i * 2 will not affect performance too much, may alter in modified sieve
							ans[j]=x;
						
						isComposite[j] = 1;
								
					}
			} 
		for (int i = 2; i < ans.length; i++) {
			System.out.println(ans[i]);
		}
	}

	
	
	
	



	private static boolean works(long mid,int[] a,int cur,long sum) {
		int i, j;
		for(i = 0, j = a.length - 1; cur> 0 && i <= j;cur--,i++,j--) {
			if(a[i] + a[j] >mid)
			{
			i--;
			}
	}
		return i>j;
	
	}


   
	static  class Scanner {
	StringTokenizer st;
	BufferedReader br;

	public Scanner(InputStream s) {
		br = new BufferedReader(new InputStreamReader(s));
	}

	public String next() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	public int[] nextIntArr(int n) throws IOException {
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = nextInt();
		return arr;
	}

	public long[] nextLongArr(int n) throws IOException {
		long[] arr = new long[n];
		for (int i = 0; i < n; i++)
			arr[i] = nextLong();
		return arr;
	}

	public long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	public String nextLine() throws IOException {
		return br.readLine();
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	public boolean ready() throws IOException {
		return br.ready();
	}
	public void waitForInput() throws InterruptedException {Thread.sleep(1000);}
}
}