#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline unsigned long long my_rand() { return rnd() + rnd(); }
int prime[100005], tot;
bool not_prime[1000005];
unsigned long long w[1000005], sum[1000005];
bool banned[1000005];
void sieve(int n) {
  not_prime[1] = true;
  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) {
      prime[++tot] = i;
    }
    for (int j = 1; j <= tot && i * prime[j] <= n; ++j) {
      not_prime[i * prime[j]] = true;
      if (i % prime[j] == 0) {
        break;
      }
    }
  }
  for (int i = 1; i <= tot; ++i) {
    int x = prime[i];
    unsigned long long cur = my_rand();
    for (int j = x; j <= n; j += x) {
      bool f = true;
      for (int y = j / x; y % x == 0; y /= x) {
        f ^= 1;
      }
      if (f) {
        w[j] ^= cur;
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    sum[i] = sum[i - 1] ^ w[i];
  }
}
void output() {}
int main() {
  sieve(1000000);
  int n;
  cin >> n;
  map<unsigned long long, int> rev;
  unsigned long long all = 0;
  auto output = [&]() {
    vector<int> p;
    for (int i = 1; i <= n; ++i) {
      if (!banned[i]) {
        p.emplace_back(i);
      }
    }
    cout << p.size() << "\n";
    for (auto x : p) {
      cout << x << " ";
    }
    exit(0);
  };
  for (int i = 1; i <= n; ++i) {
    rev[sum[i]] = i;
    all ^= sum[i];
  }
  if (!all) {
    output();
  }
  if (rev.count(all)) {
    banned[rev[all]] = true;
    output();
  }
  for (int i = 1; i <= n; ++i) {
    unsigned long long x = sum[i];
    if (rev.count(all ^ x)) {
      int j = rev[all ^ x];
      banned[i] = banned[j] = true;
      output();
    }
  }
  assert(n & 1);
  banned[n] = banned[(n - 1) / 2] = banned[2] = true;
  output();
  return 0;
}

### Prompt

Please create a solution in Cpp to 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;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline unsigned long long my_rand() { return rnd() + rnd(); }
int prime[100005], tot;
bool not_prime[1000005];
unsigned long long w[1000005], sum[1000005];
bool banned[1000005];
void sieve(int n) {
  not_prime[1] = true;
  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) {
      prime[++tot] = i;
    }
    for (int j = 1; j <= tot && i * prime[j] <= n; ++j) {
      not_prime[i * prime[j]] = true;
      if (i % prime[j] == 0) {
        break;
      }
    }
  }
  for (int i = 1; i <= tot; ++i) {
    int x = prime[i];
    unsigned long long cur = my_rand();
    for (int j = x; j <= n; j += x) {
      bool f = true;
      for (int y = j / x; y % x == 0; y /= x) {
        f ^= 1;
      }
      if (f) {
        w[j] ^= cur;
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    sum[i] = sum[i - 1] ^ w[i];
  }
}
void output() {}
int main() {
  sieve(1000000);
  int n;
  cin >> n;
  map<unsigned long long, int> rev;
  unsigned long long all = 0;
  auto output = [&]() {
    vector<int> p;
    for (int i = 1; i <= n; ++i) {
      if (!banned[i]) {
        p.emplace_back(i);
      }
    }
    cout << p.size() << "\n";
    for (auto x : p) {
      cout << x << " ";
    }
    exit(0);
  };
  for (int i = 1; i <= n; ++i) {
    rev[sum[i]] = i;
    all ^= sum[i];
  }
  if (!all) {
    output();
  }
  if (rev.count(all)) {
    banned[rev[all]] = true;
    output();
  }
  for (int i = 1; i <= n; ++i) {
    unsigned long long x = sum[i];
    if (rev.count(all ^ x)) {
      int j = rev[all ^ x];
      banned[i] = banned[j] = true;
      output();
    }
  }
  assert(n & 1);
  banned[n] = banned[(n - 1) / 2] = banned[2] = true;
  output();
  return 0;
}

```