Quadratic Set

给你 $n$ 个数 $1,2,3,\cdots,n$,构成一个集合 $A$。 称一个集合 $S$ 为**平方集合**，当且仅当 $\prod\limits_{k\in S}k!$ 是一个完全平方数。 你需要找到一个最大的集合 $A'\subseteq A$，满足 $A'$ 是一个**平方集合**。 请你求出 $A'$ 的大小以及 $A'$ 中的所有元素，注意 $A'$ 中的元素可以按照任意顺序输出。 $1\le n\le 10^6$

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 single line contains a single integer $ 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.

1

1
1

4

3
1 3 4

7

4
1 4 5 6

9

7
1 2 4 5 6 7 9