给你一个整数$$$n$$$。对于从 $$$2$$$ 到 $$$n$$$ 的每个整数 $$$i$$$,分配一个正整数 $$$a_i$$$,使得以下条件成立:
- 对于任何整数对 $$$(i,j)$$$,如果 $$$i$$$ 和 $$$j$$$ 互质,则 $$$a_i \neq a_j$$$。
- 所有 $$$a_i$$$ 的最大值应最小化(即尽可能小)。
如果一对整数的最大公约数为 $$$1$$$,则称为互质。
输入
唯一一行包含整数 $$$n$$$ ($$$2 \le n \le 10^5$$$)。
输出
打印 $$$n-1$$$ 整数、$$$a_2$$$、$$$a_3$$$、$$$\ldots$$$、$$$a_n$$$ ($$$1 \leq a_i \leq n$$$)。
如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
4
输出 #1
1 2 1
输入 #2
3
输出 #2
2 1
注意
在第一个示例中,请注意 $$$3$$$ 和 $$$4$$$ 互质,因此 $$$a_3 \neq a_4$$$。另外,请注意 $$$a=[1,2,3]$$$ 满足第一个条件,但这不是正确答案,因为它的最大值是 $$$3$$$。