C. Ehab and a Special Coloring Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 \neq 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 if their greatest common divisor is $$$1$$$.

Input

The only line contains the integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

Output

Print $$$n-1$$$ integers, $$$a_2$$$, $$$a_3$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \leq a_i \leq 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 \neq 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$$$.