在伯兰,素数很流行——受人尊敬的公民只住在有素数的楼层。钱币学家对具有主要面值的硬币评价特别高。所有黄金日均宣布放假!
然而,即便如此,也不足以让贝尔兰人民高兴。首都的大街上矗立着n栋房子,编号从1到n。政府决定把每栋房子都漆成一种颜色,这样涂成每种颜色的房子的数量之和就是素数。
然而,事实证明,并非所有公民都赞成这一决定——他们中的许多人抗议,因为他们不希望首都的主要街道上有很多彩色房屋。这就是为什么决定使用尽可能少的颜色。房屋不必连续涂漆,但 n 栋房屋中的每一栋都应涂上某种颜色。单色房屋不能连续站立,任何涂装方式都可以。
距离绘画开始只剩下不到5小时了,当每种颜色的门牌号之和为素数且使用的颜色数量最少时,帮助政府找到出路。
输入
单输入行包含一个整数 n (2 ≤ n ≤ 6000) — 首都主要街道上的房屋数量。
输出
打印n个数字的序列,其中第i个数字代表第i号门牌的颜色数。从 1 开始对颜色进行连续编号。允许任何绘画顺序。如果该问题有多种解决方案,请打印其中任何一个。如果没有这样的绘画方式,则打印单个数字-1。
示例
输入 #1
8
输出 #1
1 2 2 1 1 1 1 2