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.time.DayOfWeek;
import java.util.*;

public class d {
    FastScanner in;
    PrintWriter out;
    boolean systemIO = true;

    void solve() throws IOException {
        int n = in.nextInt();
        int arr[] = new int[n+1];
        Arrays.fill(arr, -1);
        int ans = 1;
        for (int i = 2; i <= n; i++) {
            if (arr[i] != -1) {
                continue;
            } else {
                arr[i] = ans;
                for (int j = i * 2; j <= n; j+=i) {
                    arr[j]=ans;
                }
                ans++;
            }
        }
        for (int i = 2; i <= n; i++) {
            System.out.print(arr[i]+" ");
        }


    }

    class pair {
        int a, b;

        pair(int A, int B) {
            this.a = A;
            this.b = B;
        }
    }

    private void run() throws IOException {
        if (systemIO) {
            in = new d.FastScanner(System.in);
            out = new PrintWriter(System.out);
        } else {
            in = new d.FastScanner(new File("h.in"));
            out = new PrintWriter(new File("h.out"));
        }
        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String nextLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

    }

    public static void main(String[] arg) throws IOException {
        new d().run();
    }

}