夏洛克有了一个新女朋友(和他很不一样!)。情人节快到了,他想送她一些珠宝。
他买了n件珠宝。第 i 件首饰的价格等于 i + 1,即首饰的价格为 2, 3, 4, ... n + 1。
Watson 向 Sherlock 提出了一项挑战,要求他为这些珠宝首饰上色,如果一件首饰的价格是另一件首饰价格的质因数,则两件首饰的颜色不会相同。此外,沃森要求他尽量减少使用不同颜色的数量。
帮助夏洛克完成这个琐碎的任务。
输入
唯一一行包含单个整数 n (1 ≤ n ≤ 100000) — 珠宝首饰的数量。
输出
输出的第一行应包含一个整数 k,即在给定约束下可用于为珠宝首饰着色的最小颜色数。
下一行应包含 n 个空格分隔的整数(1 到 k 之间),按价格递增的顺序指定每件的颜色。
如果有多种使用 k 种颜色为碎片着色的方法,您可以输出其中任何一种。
示例
输入 #1
3
输出 #1
2 1 1 2
输入 #2
4
输出 #2
2 2 1 1 2
注意
在第一输入中,价格分别为2、3和4的第一件、第二件和第三件珠宝的颜色分别是1、1和2。
在这种情况下,由于 2 是 4 的质因数,因此价格为 2 和 4 的珠宝的颜色必须不同。