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 cp{
	static HashSet<Integer> h = new HashSet<>();

	static void sieve()
	{
		int n = 100000;

		boolean prime[] = new boolean[n+1];
		Arrays.fill(prime,true);

		for(int i=2;i*i<n;i++)
		{
			if(prime[i])
			{
				for(int j=i*i;j<n;j+=i)
					prime[j]=false;
			}
		}

		for(int i=2;i<n;i++)
		{
			if(prime[i])
				h.add(i);
		}
		//out.println(h);
			
	}
    public static void main(String[] args) {
        Scanner sc = new Scanner();
       sieve();
        int n = sc.nextInt();

        int ar[] = new int[n+1];
        int count = 1;
        for(int i=2;i<=n;i++)
        {
        	if(h.contains(i))
        	{
        		ar[i]=count;

        		for(int j=i;j<=n;j+=i)
        			ar[j]=count;
        		count++;
        	}
        }
      for(int i=2;i<=n;i++)
      	out.print(ar[i]+" ");
        	out.close();
        
    }//2 3 4 5 6 7 8 9 10
	 //1 2 1 3 1 4 1 2 1

    static  PrintWriter out=new PrintWriter(System.out);
    static class Scanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        String nextLine() {
            while (!st.hasMoreTokens())
                try { 
                                        st=new StringTokenizer(br.readLine());                             
                                } catch (IOException e) {}
            return st.nextToken();
        }
        char nextChar() {
            char c = '$';
                try { 
                                        c = (char)br.read();                           
                                } catch (IOException e) {}
            return c;
        }       
        int nextInt() {
            return Integer.parseInt(nextLine());
        }
        Double nextDouble() {
            return Double.parseDouble(nextLine());
        }
        long nextLong() {
            return Long.parseLong(nextLine());
        }
    }
}

//vvovvovvovvovv
//1203405607809(10)

//2*8