Sherlock has a new girlfriend (so unlike him!). Valentine's day is coming and he wants to gift her some jewelry.
He bought $n$ pieces of jewelry. The $i$-th piece has price equal to $i+1$, that is, the prices of the jewelry are $2,3,4,...,n+1$.
Watson gave Sherlock a challenge to color these jewelry pieces such that two pieces don't have the same color if the price of one piece is a prime divisor of the price of the other piece. Also, Watson asked him to minimize the number of different colors used.
Help Sherlock complete this trivial task.


Sherlock 有了一个新女友（这太不像他了！）。情人节到了，他想送给女友一些珠宝当做礼物。
他买了 $n$ 件珠宝。第 $i$ 件的价值是 $i+1$。那就是说，珠宝的价值分别为 $2,3,4,...,n+1$。
Watson 挑战 Sherlock，让他给这些珠宝染色，使得一件珠宝的价格是另一件的质因子时，两件珠宝的颜色不同。并且，Watson 要求他最小化颜色的使用数。
请帮助 Sherlock 完成这个简单的任务。

The only line contains single integer $n\ (1≤n≤100000)$− the number of jewelry pieces.
只有一行一个整数 $n$，表示珠宝件数。

The first line of output should contain a single integer $k$, the minimum number of colors that can be used to color the pieces of jewelry with the given constraints.
The next line should consist of $n$ space-separated integers (between $1$ and $k$) that specify the color of each piece in the order of increasing price.
If there are multiple ways to color the pieces using $k$ colors, you can output any of them.
第一行一个整数 $k$，表示最少的染色数；
第二行 $n$ 个整数，表示第 $1$ 到第 $n$ 件珠宝被染成的颜色。若有多种答案，输出任意一种。

对于全部数据，$1 \leq n \leq 10^5$。

2
1 1 2

the colors for first, second and third pieces of jewelry having respective prices $2, 3$ and $4$ are $1$, $1$ and $2$ respectively.

2
2 1 1 2

as $2$ is a prime divisor of $4$, colors of jewelry having prices $2$ and $4$ must be distinct.
因为 $2$ 是 $4$ 的一个质因子，因此第一件珠宝与第三件珠宝的颜色必须不同。