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.lang.reflect.Array;
        import java.util.*;
import java.util.function.Predicate;

public class Main {
    static class FastScanner {
        private BufferedReader bufferedReader;
        private StringTokenizer stringTokenizer;
        public FastScanner(InputStream inputStream){
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
        }
        public String next() {
            while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()){
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException ignored){}
            }
            return stringTokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    static class Node implements Comparable {
        Node left;
        Node right;
        private int value;

        Node(Node left, Node right, int value) {
            this.left = left;
            this.right = right;
            this.value = value;
        }

        @Override
        public int compareTo(Object o) {
            return Integer.compare(this.value, ((Node)o).value);
        }
    }

    private static int fib(int n, int m){
        if (n < 2) return n;
        int a = 0;
        int b = 1;
        for (int i=0;i<n-2;i++){
            int c = (a + b) % m;
            a = b;
            b = c;
        }
        return (a + b) % m;
    }

    static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    static long lcm(long a, long b) {
        return Math.abs(a * b) / gcd(a, b);
    }

    static class DSU {
        private int [] p;
        private int [] r;

        DSU(int n) {
            p = new int[n];
            r = new int[n];
            Arrays.fill(p, -1);
            Arrays.fill(r, 0);
        }

        int find(int x) {
            if (p[x] < 0) {
                return x;
            }
            return p[x] = find(p[x]);
        }

        void union(int a, int b) {
            a = find(a);
            b = find(b);
            if (a == b) return;
            if (r[a] < r[b]) {
                p[a] = b;
            }
            else {
                p[b] = a;
            }
            if (r[a] == r[b]) {
                r[a] ++;
            }
        }
    }

    private static boolean isPrime(long n) {
        for (int i = 2; i < n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    private static final int N = (int) 10e5 + 1;
    private static final long MOD = 1000000007;

    private static long []dp = new long[N];
    private static long []dp2 = new long[N];

    static {
        Arrays.fill(dp, -1);
        Arrays.fill(dp2, 0);
    }

    private static long cnt(int n, int k) {
        if (dp[n] == -1) {
            if (n < k) dp[n] = 1;
            else dp[n] = (cnt(n-1, k) + cnt(n-k, k)) % MOD;
        }
        return dp[n] % MOD;
    }

    private static ArrayList<Map.Entry<Integer, Integer>>exclude(ArrayList<Map.Entry<Integer, Integer>>a, int x) {
        ArrayList<Map.Entry<Integer, Integer>>b = new ArrayList<>(a.size());
        for (int i = 0; i < a.size(); i++) {
            if (a.get(i).getValue() == x || a.get(i).getKey() == x) continue;
            b.add(a.get(i));
        }
        return b;
    }

    private static double med(Integer[]a) {
        Arrays.sort(a);
        if (a.length % 2 == 0) {
            int r = a.length / 2;
            int l = r-1;
            double s = a[l] + a[r];
            return s / 2.0;
        }
        int m = a.length / 2;
        return a[m];
    }

    static Map<Integer, ArrayList<Integer>>g;
    static Map<Integer, Integer> color;

    static void dfs(int v, int c) {
        color.put(v, c);
        for (int i = 0; i < g.get(v).size(); i++) {
            int u = g.get(v).get(i);
            if (!color.containsKey(u)) {
                dfs(u, c);
            }
        }
    }

    static void reverse(Integer a[]) {
        Collections.reverse(Arrays.asList(a));
    }

    static boolean next(Integer []a) {
        int i = a.length - 1;
        while(a[i] == 0) i--;
        int c = 0;
        while(i >= 0 && a[i] == 1) {
            c++;
            i--;
        }
        if (i < 0) return false;
        a[i] = 1;
        for (int j = i + 1; j < a.length; j++) {
            a[j] = 0;
        }
        c--;
        for (int j = 0; j < c; j++) {
            a[a.length - 1 - j] = 1;
        }
        return true;
    }

    private static int bin(Integer []a, int l, int r, int x){
        if (l >= r) return l;
        int m = (l + r) / 2;
        if (a[m] > x) {
            return bin(a, l, m, x);
        }
        else if (a[m] < x || (m < a.length - 1 && a[m+1] == x)){
            return bin(a, m + 1, r, x);
        }
        return m + 1;
    }

    static class E{
        int v;
        int index;
    }

    public static void main(String[] args){
        FastScanner scanner = new FastScanner(System.in);
        PrintWriter printer = new PrintWriter(System.out);
        int n = scanner.nextInt(), c = 0;
        Integer []a = new Integer[100005];
        for (int i = 0; i < a.length; i++) {
            a[i] = 0;
        }
        for (int i = 2; i <= n; i++) {
            if (a[i] == 0) {
                a[i] = ++c;
                for (int j = i + i; j <= n; j+=i) {
                    a[j] = a[i];
                }
            }
        }
        for (int i = 2; i <= n; i++) {
            printer.print(a[i] + " ");
        }
        printer.flush();
        printer.close();
    }
}