#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> sm_prime(1000006, 0);
unordered_map<int, long long> hash_prime;
mt19937_64 rng;
void print(vector<int> avoid) {
  cout << n - avoid.size() << "\n";
  for (int i = 1; i <= n; i++) {
    if (find(avoid.begin(), avoid.end(), i) == avoid.end()) {
      cout << i << " ";
    }
  }
  exit(0);
}
void solve() {
  cin >> n;
  vector<long long> num_hash(n + 1, 0);
  for (int i = 2; i <= n; i++) {
    num_hash[i] = num_hash[i / sm_prime[i]] ^ hash_prime[sm_prime[i]];
  }
  vector<long long> fac_hash(n + 1, 0);
  for (int i = 2; i <= n; i++) {
    fac_hash[i] = fac_hash[i - 1] ^ num_hash[i];
  }
  long long all_hash = 0;
  for (int i = 1; i <= n; i++) {
    all_hash ^= fac_hash[i];
  }
  if (all_hash == 0) {
    print({});
  }
  for (int i = 1; i <= n; i++) {
    if (all_hash == fac_hash[i]) {
      print({i});
    }
  }
  unordered_map<long long, int> index;
  for (int i = 1; i <= n; i++) {
    long long wanted = all_hash ^ fac_hash[i];
    if (index.count(wanted) > 0) {
      print({i, index[wanted]});
    }
    index[fac_hash[i]] = i;
  }
  print({2, (n - 1) / 2, n});
}
void pre() {
  vector<bool> is_prime(1000006, true);
  for (int i = 2; i < 1000006; i++) {
    if (is_prime[i]) {
      sm_prime[i] = i;
      hash_prime[i] = rng();
      if ((long long)i * i >= 1000006) continue;
      for (int j = i * i; j < 1000006; j += i) {
        if (is_prime[j]) {
          is_prime[j] = false;
          sm_prime[j] = i;
        }
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  rng = mt19937_64(time(NULL));
  pre();
  int t = 1;
  while (t--) {
    solve();
  }
}

### Prompt

Develop a solution in cpp to the problem described below:

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;
int n;
vector<int> sm_prime(1000006, 0);
unordered_map<int, long long> hash_prime;
mt19937_64 rng;
void print(vector<int> avoid) {
  cout << n - avoid.size() << "\n";
  for (int i = 1; i <= n; i++) {
    if (find(avoid.begin(), avoid.end(), i) == avoid.end()) {
      cout << i << " ";
    }
  }
  exit(0);
}
void solve() {
  cin >> n;
  vector<long long> num_hash(n + 1, 0);
  for (int i = 2; i <= n; i++) {
    num_hash[i] = num_hash[i / sm_prime[i]] ^ hash_prime[sm_prime[i]];
  }
  vector<long long> fac_hash(n + 1, 0);
  for (int i = 2; i <= n; i++) {
    fac_hash[i] = fac_hash[i - 1] ^ num_hash[i];
  }
  long long all_hash = 0;
  for (int i = 1; i <= n; i++) {
    all_hash ^= fac_hash[i];
  }
  if (all_hash == 0) {
    print({});
  }
  for (int i = 1; i <= n; i++) {
    if (all_hash == fac_hash[i]) {
      print({i});
    }
  }
  unordered_map<long long, int> index;
  for (int i = 1; i <= n; i++) {
    long long wanted = all_hash ^ fac_hash[i];
    if (index.count(wanted) > 0) {
      print({i, index[wanted]});
    }
    index[fac_hash[i]] = i;
  }
  print({2, (n - 1) / 2, n});
}
void pre() {
  vector<bool> is_prime(1000006, true);
  for (int i = 2; i < 1000006; i++) {
    if (is_prime[i]) {
      sm_prime[i] = i;
      hash_prime[i] = rng();
      if ((long long)i * i >= 1000006) continue;
      for (int j = i * i; j < 1000006; j += i) {
        if (is_prime[j]) {
          is_prime[j] = false;
          sm_prime[j] = i;
        }
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  rng = mt19937_64(time(NULL));
  pre();
  int t = 1;
  while (t--) {
    solve();
  }
}

```