该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

恰逢 H 国国庆，国王邀请 $n$ 位大臣来玩一个游戏。首先，他给大臣们编号为 2 ~ n+1。然后国王准备了很多有颜色的帽子，让每个大臣去挑选一顶帽子戴上。但是国王有规定：对于任意两个大臣，如果一个大臣的编号是另外一个大臣的编号的质因子，则他们两人不能戴相同颜色的帽子。

国王想知道，他最少需要准备多少种颜色的帽子？

自然地，这个任务交给了你。

首先，你需要输出一个数 k，表示国王需要准备的帽子的最少颜色种数。

然后，你还需要输出一种合法方案，即输出 n 个数 c1, c2, ..., cn，分别表示 2, 3, ..., n+1 号大臣所戴帽子的颜色。颜色用 1 ~ k 之间的整数表示。如果有多种合法方案，则输出任意一种即可。

输入格式

一个整数 $n$，表示大臣的人数。

输出格式

第一行：一个整数 k

第二行：n 个数 c1, c2, ..., cn，数之间以一个空格隔开

样例输入 1

3

样例输出 1

2
1 1 2

样例输入 2

4

样例输出 2

2
2 1 1 2

数据范围

对于 $100\%$ 的数据，有 $1 ≤ n ≤100,000$