CF776B.Sherlock and his girlfriend

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.

夏洛克有了一个新女友（这可真不像他！）。情人节即将到来，他想送她一些珠宝。

他买了 $n$ 件珠宝。第 $i$ 件珠宝的价格为 $i+1$，即这些珠宝的价格依次为 $2,\,3,\,4,\,\dots,\,n+1$。

华生给夏洛克出了一个挑战：对这些珠宝进行染色，要求若某件珠宝的价格是另一件珠宝价格的质因数，则这两件珠宝不能染成相同的颜色。此外，华生还要求所用颜色的种类数尽可能少。

请帮助夏洛克完成这项看似简单的任务。

The only line contains single integer n (1 ≤ n ≤ 100000) — the number of jewelry pieces.

唯一的一行包含一个整数 $n$（$1 \leq n \leq 100000$）——珠宝的数量。

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$ 到 $k$），表示按价格升序排列的每件珠宝碎片所分配的颜色。

若存在多种使用 $k$ 种颜色完成着色的方案，输出任意一种即可。

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

In this case, as 2 is a prime divisor of 4, colors of jewelry having prices 2 and 4 must be distinct.

在第一组输入中，价格分别为 2、3 和 4 的前三件首饰的颜色依次为 1、1 和 2。

本例中，由于 2 是 4 的一个质因数，因此价格为 2 和 4 的首饰颜色必须不同。