题目描述

Sherlock 有一个新女朋友。现在情人节就要到了，他想送给她一些珠宝。

他买了几件首饰。第 $i$ 件的价格等于 $i+ 1$，也就是说，珠宝的价格分别为 $2,3,4,\ldots,n + 1$ 。

现在需要给这些珠宝首饰上色。当一件珠宝的价格是另一件珠宝的价格的素因子时，这两件的颜色就不允许相同。 此外，要最少化使用的颜色数量。

输入格式

一行，包含单个整数 $n(1\le n\leq 100000)$ 指珠宝的数量。

输出格式

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

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

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

输入输出样例 #1

输入 #1

3

输出 #1

2
1 1 2 

输入输出样例 #2

输入 #2

4

输出 #2

2
2 1 1 2

说明/提示

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

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