#include <bits/stdc++.h>
using namespace std;
long long fastpow(long long a, long long b,
                  long long m = (long long)(1e9 + 7)) {
  long long res = 1;
  a %= m;
  while (b > 0) {
    if (b & 1) res = (res * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return res;
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
signed main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  ;
  long long n;
  cin >> n;
  if (n == 1) {
    cout << "1\n1\n";
    exit(0);
  }
  vector<long long> primes(n + 1);
  vector<long long> prime_hash(n + 1, 0);
  iota(primes.begin(), primes.end(), 0);
  for (long long i = 2; i <= n; i++) {
    if (primes[i] == i) {
      for (long long j = i; j <= n; j += i) {
        primes[j] = min(primes[j], i);
      }
      prime_hash[i] = rng();
    }
  }
  vector<long long> fact_hash(n + 1, 0);
  map<long long, long long> rev_fact_hash;
  for (long long i = 2; i <= n; i++) {
    fact_hash[i] = fact_hash[i - 1];
    long long x = i;
    while (x != 1) {
      fact_hash[i] ^= prime_hash[primes[x]];
      x = x / primes[x];
    }
    rev_fact_hash[fact_hash[i]] = i;
  }
  long long cum_hash = 0;
  for (long long i = 1; i <= n; i++) {
    cum_hash ^= fact_hash[i];
  }
  vector<long long> remove;
  if (cum_hash != 0) {
    if (rev_fact_hash.find(cum_hash) != rev_fact_hash.end()) {
      remove.push_back(rev_fact_hash[cum_hash]);
    } else {
      for (long long i = 2; i <= n; i++) {
        long long new_hash = cum_hash ^ fact_hash[i];
        if (rev_fact_hash.find(new_hash) != rev_fact_hash.end()) {
          remove = {i, rev_fact_hash[new_hash]};
          break;
        }
      }
    }
    if ((long long)remove.size() == 0) {
      n--;
      remove = {2, n / 2};
    }
  }
  cout << n - (long long)remove.size() << "\n";
  for (long long i = 1; i <= n; i++) {
    if (find(remove.begin(), remove.end(), i) == remove.end()) cout << i << " ";
  }
  cout << "\n";
  return 0;
}

### Prompt

Generate a cpp solution 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;
long long fastpow(long long a, long long b,
                  long long m = (long long)(1e9 + 7)) {
  long long res = 1;
  a %= m;
  while (b > 0) {
    if (b & 1) res = (res * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return res;
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
signed main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  ;
  long long n;
  cin >> n;
  if (n == 1) {
    cout << "1\n1\n";
    exit(0);
  }
  vector<long long> primes(n + 1);
  vector<long long> prime_hash(n + 1, 0);
  iota(primes.begin(), primes.end(), 0);
  for (long long i = 2; i <= n; i++) {
    if (primes[i] == i) {
      for (long long j = i; j <= n; j += i) {
        primes[j] = min(primes[j], i);
      }
      prime_hash[i] = rng();
    }
  }
  vector<long long> fact_hash(n + 1, 0);
  map<long long, long long> rev_fact_hash;
  for (long long i = 2; i <= n; i++) {
    fact_hash[i] = fact_hash[i - 1];
    long long x = i;
    while (x != 1) {
      fact_hash[i] ^= prime_hash[primes[x]];
      x = x / primes[x];
    }
    rev_fact_hash[fact_hash[i]] = i;
  }
  long long cum_hash = 0;
  for (long long i = 1; i <= n; i++) {
    cum_hash ^= fact_hash[i];
  }
  vector<long long> remove;
  if (cum_hash != 0) {
    if (rev_fact_hash.find(cum_hash) != rev_fact_hash.end()) {
      remove.push_back(rev_fact_hash[cum_hash]);
    } else {
      for (long long i = 2; i <= n; i++) {
        long long new_hash = cum_hash ^ fact_hash[i];
        if (rev_fact_hash.find(new_hash) != rev_fact_hash.end()) {
          remove = {i, rev_fact_hash[new_hash]};
          break;
        }
      }
    }
    if ((long long)remove.size() == 0) {
      n--;
      remove = {2, n / 2};
    }
  }
  cout << n - (long long)remove.size() << "\n";
  for (long long i = 1; i <= n; i++) {
    if (find(remove.begin(), remove.end(), i) == remove.end()) cout << i << " ";
  }
  cout << "\n";
  return 0;
}

```