776B Sherlock and his girlfriend

题目描述

福尔摩斯交了个新女友（这可真不像他！）。情人节就要到了，他想送她一些首饰。

他买了 n 件首饰。第 i 件首饰的价格是 i + 1，也就是说，这些首饰的价格依次为 2, 3, 4, … n + 1。

华生给福尔摩斯出了道挑战题：给这些首饰染色。如果一件首饰的价格是另一件首饰价格的质因数，那么它们必须染成不同的颜色。华生还要求，使用的颜色种类要尽可能少。

帮福尔摩斯完成这个简单的小任务吧。

输入格式

仅一行，包含一个整数 n（1 ≤ n ≤ 100000）——首饰的数量。

输出格式

第一行输出一个整数 k，表示满足条件所需的最少颜色数。

第二行输出 n 个以空格分隔的整数（范围在 1 到 k 之间），按首饰价格从小到大的顺序给出每件首饰的颜色。

如果有多种使用 k 种颜色的染色方案，输出任意一种即可。

说明

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

因为 2 是 4 的质因数，所以价格为 2 和 4 的首饰必须使用不同颜色。

输入输出样例 #1

输入 #1

13

输出 #1

1
22
1 1 2

输入输出样例 #2

输入 #2

14

输出 #2

1
22
2 1 1 2