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.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.*;

public class R563C {
	static boolean[] prime;
	public static void main(String[] args) {
		JS scan = new JS();
		int n = scan.nextInt();
		prime = new boolean[n+10];
		PrintWriter out = new PrintWriter(System.out);
		sieve(n+5);
		Integer[] ans = new Integer[n+1];
		boolean[] seen = new boolean[n+1];
		Arrays.fill(ans, -1);
		for(int i = 2;i<=n;i++){
				
				if(prime[i]){
					long aba = i;
					if(aba*aba<=n){
					
						ans[i] = i;
						seen[i] = true;
					}
				}
				for(int j = 2;j<=Math.sqrt(i);j++){
					if(i%j==0){
						ans[i] = j;
						seen[j] =true;
						break;
					}
				}
		}
		int idx = 2;
		int max = -1;
		for(int i = 2;i<=n;i++){	
			if(ans[i]==-1){
				while(seen[idx]){
					idx++;
				}
				seen[idx] = true;
				ans[i] = idx;
			}
			max = Math.max(max, ans[i]);
		}
		for(int i = 2;i<=n;i++){
			if(ans[i] == max){
				out.print(1+" ");
			}
			else
			out.print(ans[i]+" ");
			
		}
//		for(int i = 2;i<=n;i++){
//			for(int j =2;j<=n;j++){
//				if(i==j)continue;
//				if(gcd(i,j)==1 && ans[i]==ans[j])System.out.println("wtf");
//			}
//		}
		out.flush();
		out.close();
		
		
	}
	// 2 3 5 7 11 13 17 19 23 29 31 37
	static int gcd(int a, int b) 
    { 
        if (a == 0 || b == 0) 
            return 0; 
          
        if (a == b) 
            return a; 
          
        if (a > b) 
            return gcd(a-b, b); 
                  
        return gcd(a, b-a); 
    } 
	public static void sieve(int n) 
    { 
        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; 
            } 
        } 
          
    } 
	  
	static class JS{
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public JS() {
			in = new BufferedInputStream(System.in, BS);
		}

		public JS(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}				
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
	}
}