题目描述

Sherlock 有 $n$ 件珠宝，第 $i$ 件珠宝的价值是 $i+1$（即价值分别为 $2, 3, 4, \dots, n+1$）。
要求给珠宝染色，使得：如果一件珠宝的价值是另一件珠宝价值的质因子，那么它们的颜色必须不同。要求最小化颜色种类数，并输出染色方案。

输入格式

一行一个整数 $n$，表示珠宝数量。

输出格式

第一行一个整数 $k$，表示最少需要的颜色数。
第二行 $n$ 个整数，表示珠宝 $1$ 到 $n$ 的颜色（按价值 $2, 3, \dots, n+1$ 的顺序）。
注意颜色从 $1$ 开始编号，值不超过 $k$。

3

2
1 1 2

4

2
2 1 1 2

数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 10^5$。