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.lang.Math.*;
import java.io.*;
import java.util.PriorityQueue;

/**
 */
public class Solution {

    Solution() {
        ;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>();
        HashMap<Integer, Integer> hmap = new HashMap<Integer, Integer>();
        //int t = in.nextInt();  // Scanner has functions to read ints, longs, strings, chars, etc.
        int t = 1;  // Scanner has functions to read ints, longs, strings, chars, etc.
        int N;
        int L;
        Solution recurSol = new Solution();
        String   soln;
        StringBuilder sol = new StringBuilder();
        sol.setLength(0);
        int[]    input;

        for (int i = 1; i <= t; ++i) {

            /** Integer followed by multiple integers. */
            /**
            N = in.nextInt();
            input = new int[N];
            for (int j = 0; j < N; ++j) {
                input[j] = in.nextInt();
            }
             */

            // Alphanumeric input spanning multiple lines.
              N = in.nextInt();
              int prevVal = 0;

              for (int j = 2; j < N + 1; ++j) {
                if (recurSol.isPrime(j)) {
                    hmap.put(j, prevVal + 1);
                    sol.append(prevVal + 1);
                    prevVal++;
                } else {
                    Iterator hmIterator = hmap.entrySet().iterator();
                    while (hmIterator.hasNext()) {
                        Map.Entry mapElement = (Map.Entry)hmIterator.next();
                        if (j % (int)(mapElement.getKey()) == 0) {
                            sol.append(mapElement.getValue());
                            break;
                        }
                    }
                }
                if (j < N)
                    sol.append(" ");
              }
              System.out.println(sol.toString());
        }
    }

    public boolean isPrime(int n) {
        int i;
        int k;

        if (n == 2 || n == 3)
            return true;
        if (n == 4)
            return false;
        for (i = 2; i * i <= n; ++i) {
            k = n % i;
            if (k == 0) {
                return false;
            }
        }
        return true;
    }

    public class maxComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer x, Integer y) {
            if (x > y)
                return -1;
            else if (x == y)
                return 0;
            else
                return 1;
        }
    }

 }