← 返回题目列表

Codeforces · 1622/F

F. 二次集

中文机器翻译题面 查看原题

如果一组正整数 $$$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