#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 2;
unsigned long long h[N];
int p[N];
bool ed[N], flg[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
  unordered_map<unsigned long long, int> mp;
  int n, m = 0, i, j, k;
  unsigned long long tot = 0;
  cin >> n;
  for (i = 2; i <= n; i++) {
    if (!ed[i]) p[m++] = i, h[i] = rnd();
    for (j = 0; j < m && (k = i * p[j]) <= n; j++) {
      ed[k] = 1;
      h[k] = h[i] ^ h[p[j]];
      if (i % p[j] == 0) break;
    }
    if (1 ^ n - i & 1) tot ^= h[i];
  }
  for (i = 3; i <= n; i++) h[i] ^= h[i - 1];
  fill(flg + 1, flg + n + 1, 1);
  if (tot == 0) goto out;
  for (i = 1; i <= n; i++)
    if (tot == h[i]) {
      flg[i] = 0;
      goto out;
    }
  for (i = 1; i <= n; i++) {
    auto it = mp.find(tot ^ h[i]);
    if (it != mp.end()) {
      flg[i] = flg[it->second] = 0;
      goto out;
    }
    mp[h[i]] = i;
  }
  flg[n >> 1] = flg[2] = flg[n] = 0;
out:
  cout << accumulate(flg + 1, flg + n + 1, 0) << '\n';
  for (int i = 1; i <= n; i++)
    if (flg[i]) cout << i << ' ';
}

### Prompt

Create a solution in CPP for the following problem:

Let's call a set of positive integers a_1, a_2, ..., a_k quadratic if the product of the factorials of its elements is a square of an integer, i. e. ∏_{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, ..., n of maximum size. If there are multiple answers, print any of them.

Input

A single line contains a single integer n (1 ≤ n ≤ 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.

Examples

Input


1


Output


1
1 


Input


4


Output


3
1 3 4 


Input


7


Output


4
1 4 5 6 


Input


9


Output


7
1 2 4 5 6 7 9 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 2;
unsigned long long h[N];
int p[N];
bool ed[N], flg[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
  unordered_map<unsigned long long, int> mp;
  int n, m = 0, i, j, k;
  unsigned long long tot = 0;
  cin >> n;
  for (i = 2; i <= n; i++) {
    if (!ed[i]) p[m++] = i, h[i] = rnd();
    for (j = 0; j < m && (k = i * p[j]) <= n; j++) {
      ed[k] = 1;
      h[k] = h[i] ^ h[p[j]];
      if (i % p[j] == 0) break;
    }
    if (1 ^ n - i & 1) tot ^= h[i];
  }
  for (i = 3; i <= n; i++) h[i] ^= h[i - 1];
  fill(flg + 1, flg + n + 1, 1);
  if (tot == 0) goto out;
  for (i = 1; i <= n; i++)
    if (tot == h[i]) {
      flg[i] = 0;
      goto out;
    }
  for (i = 1; i <= n; i++) {
    auto it = mp.find(tot ^ h[i]);
    if (it != mp.end()) {
      flg[i] = flg[it->second] = 0;
      goto out;
    }
    mp[h[i]] = i;
  }
  flg[n >> 1] = flg[2] = flg[n] = 0;
out:
  cout << accumulate(flg + 1, flg + n + 1, 0) << '\n';
  for (int i = 1; i <= n; i++)
    if (flg[i]) cout << i << ' ';
}

```