CF1622F.Quadratic Set

Let's call a set of positive integers $a_1, a_2, \dots, a_k$ quadratic if the product of the factorials of its elements is a square of an integer, i. e. $\prod\limits_{i=1}^{k} a_i! = m^2$, for some integer $m$.

You are given a positive integer $n$.

Your task is to find a quadratic subset of a set $1, 2, \dots, n$ of maximum size. If there are multiple answers, print any of them.

我们称一个正整数集合 $a_1, a_2, \dots, a_k$ 是二次的（quadratic），如果其各元素的阶乘之积是一个整数的平方，即 $\prod\limits_{i=1}^{k} a_i! = m^2$，其中 $m$ 为某个整数。

给定一个正整数 $n$。

你的任务是在集合 $\{1, 2, \dots, n\}$ 中找出一个最大规模的二次子集。若存在多个满足条件的答案，输出任意一个即可。

A single line contains a single integer $n$ ($1 \le n \le 10^6$).

一行中包含一个整数 $n$（$1 \le n \le 10^6$）。

In the first line, print a single integer — the size of the maximum subset. In the second line, print the subset itself in an arbitrary order.

第一行输出一个整数——最大子集的大小。
第二行以任意顺序输出该子集本身。