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.

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$.