如果一组正整数 $$$a_1, a_2, \dots, a_k$$$ 其元素阶乘的乘积是整数 i 的平方,那么我们将其称为二次方。 e. $$$\prod\limits_{i=1}^{k} a_i! = m^2$$$,对于某个整数 $$$m$$$。
给你一个正整数$$$n$$$。
你的任务是找到最大尺寸 $$$1, 2, \dots, n$$$ 集合的二次子集。如果有多个答案,请打印其中任何一个。
输入
单行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$)。
输出
在第一行中,打印一个整数 - 最大子集的大小。在第二行中,以任意顺序打印子集本身。
示例
输入 #1
1
输出 #1
1 1
输入 #2
4
输出 #2
3 1 3 4
输入 #3
7
输出 #3
4 1 4 5 6
输入#4
9
输出#4
7 1 2 4 5 6 7 9