Quadratic Set
Description
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.
Input
A single line contains a single integer $n$ ($1 \le n \le 10^6$).
Output
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.
Samples
1
1
1
4
3
1 3 4
7
4
1 4 5 6
9
7
1 2 4 5 6 7 9