C. [CF 776B]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块珠宝涂色（编号为1-n），其中第 i 块珠宝的价格为 i+1 。规定：如果一块珠宝的价格 是 另一块珠宝价格 的质因子，那么这两块珠宝不能涂同样的颜色。其中颜色用数字表示（即同样的数字表示同样的暗色）。题目要求输出：第一行输出最少使用的颜色数量，第二行输出1-n块珠宝的颜色（颜色用数字表示，从1开始）。如果有多种情况，那么输出任意一种。

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

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.