1150: 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 nn pieces of jewelry. The ii -th piece has price equal to i+1i+1 , that is, the prices of the jewelry are 2,3,4,...\ n+12,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有一个新女朋友（真不像他！）情人节就要到了，他想送给她一些珠宝。 他买了几件首饰。第i件的价格等于i+ 1，也就是说，珠宝的价格为2、3、4、…n + 1。

Watson给Sherlock一个挑战：给这些珠宝首饰上色，当一件的价格是另一间的价格的素因子时，使得这两件两件没有相同的颜色。此外，Watson要求他使用的尽量少种颜色。

请帮助Sherlock完成这个琐碎的任务。

输入输出格式： 输入格式： 一行，包含单个整数n（1＜n<＝100000）指珠宝的数量。

输出格式 第一行的输出包含一个整数K，指最少种颜色的数量。

第二行由n个整数（1到k）组成，按价格从小到大来表示每件珠宝的颜色。

如果有多种方法，则可以输出它们中的任何一种。

说明 在第一个样例中，第一、第二和第三件首饰的价格分别为2、3、4,它们的颜色分别为1、1和2。

在这种情况下，由于2是4的因子，所以具有因数2和4的珠宝的颜色必须是不同的。

The only line contains single integer n ( 1<=n<=100000 ) — the number of jewelry pieces.
输入格式： 一行，包含单个整数n（1＜=n<＝100000）指珠宝的数量。

The first line of output should contain a single integer kk , 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 nn space-separated integers (between 11 and kk ) that specify the color of each piece in the order of increasing price.

If there are multiple ways to color the pieces using kk colors, you can output any of them.


第一行的输出包含一个整数K，指最少种颜色的数量。

第二行由n个整数（1到k）组成，按价格从小到大来表示每件珠宝的颜色。

3

2
1 1 2