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

public class Above80 {

	public static void main(String[] args) throws IOException,NumberFormatException {
		try {
			FastScanner sc=new FastScanner();
			int n=sc.nextInt();
			int max=3;
			Map<Integer,Integer> map=new HashMap<>();
			map.put(2,1);
			map.put(3,2);
			for(int i=2;i<=n;i++) {
				if(i%2==0)
					System.out.print(1+" ");
				else {
					int factor=1;
					if(map.containsKey(i)) {
						System.out.print(map.get(i)+" ");
						continue;
					}
					for(int j=3;j*j<=i;j++) {
						if(i%j==0) {
							factor=j;
							break;
						}
					}
					if(factor==1) {
						System.out.print(max+" ");
						map.put(i,max);
						max++;
					}
					else {
						System.out.print(map.get(factor)+" ");
						map.put(i,map.get(factor));
					}
				}
			}
			
			 
		}
		catch(Exception e){
			return;
		}

	}

	public static boolean isPalindrome(String s) {
	  char a[]=s.toCharArray();
	  for(int i=0,j=a.length-1;i<a.length/2;i++,j--) {
		  if(a[i]!=a[j])
			  return false;
	  }
	  return true;
	}
	public static long solve(long n) {
		long sum=1;
		for(long i=2;i*i<=n;i++) {
			long count=0;
			if(n%i==0) {
				while(n%i==0) {
					count++;
					n/=i;
				}
				sum*=(count+1);
			}
		}
		if(n>1)
			sum*=2;
		return sum;
	}
	public static boolean isPrime(int n) {
		if(n==1)
			return false;
		for(int i=2;i*i<=n;i++) {
			if(n%i==0)
				return false;
		}
		return true;
		
	}
	public static class FastScanner {
		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) {}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		
	}

}