#include <bits/stdc++.h>
using namespace std;
bool is_perfect_square(unsigned long long int n) {
  if (pow((long int)(sqrt(n)), 2) == n) {
    return true;
  }
  return false;
}
void solve() {
  unsigned long int n;
  cin >> n;
  vector<unsigned long int> arr = {};
  unsigned long int halfi = (long int)n / 2;
  unsigned long long int asdf =
      (unsigned long long int)2 * (halfi) * (halfi - 1);
  if ((n % 4) == 0) {
    arr = {halfi};
  } else if (n == 1) {
    arr = {};
  } else if (n % 4 == 1) {
    arr = {halfi, n};
  } else if ((n % 4) == 2) {
    if (is_perfect_square((unsigned long long int)(n + 2)))
      arr = {halfi + 1};
    else if (is_perfect_square((unsigned long long int)(n * (halfi - 1))))
      arr = {halfi - 2};
    else
      arr = {halfi, 2};
  } else {
    if (is_perfect_square((unsigned long long int)(n + 1)))
      arr = {halfi + 1, n};
    else if (is_perfect_square(asdf))
      arr = {n, halfi - 2};
    else if (is_perfect_square(((long long int)halfi - 1) * (long long int)n))
      arr = {halfi - 2, n - 2};
    else
      arr = {2, halfi, n};
  }
  vector<int> ans = {};
  for (int i = 1; i < n + 1; i++) {
    if (find(arr.begin(), arr.end(), i) == arr.end()) ans.push_back(i);
  }
  cout << ans.size() << endl;
  for (int el = 0; el < ans.size(); el++) {
    cout << ans[el] << ' ';
  }
  cout << endl;
}
int main() {
  solve();
  return 0;
}

### Prompt

Please provide a CPP coded solution 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;
bool is_perfect_square(unsigned long long int n) {
  if (pow((long int)(sqrt(n)), 2) == n) {
    return true;
  }
  return false;
}
void solve() {
  unsigned long int n;
  cin >> n;
  vector<unsigned long int> arr = {};
  unsigned long int halfi = (long int)n / 2;
  unsigned long long int asdf =
      (unsigned long long int)2 * (halfi) * (halfi - 1);
  if ((n % 4) == 0) {
    arr = {halfi};
  } else if (n == 1) {
    arr = {};
  } else if (n % 4 == 1) {
    arr = {halfi, n};
  } else if ((n % 4) == 2) {
    if (is_perfect_square((unsigned long long int)(n + 2)))
      arr = {halfi + 1};
    else if (is_perfect_square((unsigned long long int)(n * (halfi - 1))))
      arr = {halfi - 2};
    else
      arr = {halfi, 2};
  } else {
    if (is_perfect_square((unsigned long long int)(n + 1)))
      arr = {halfi + 1, n};
    else if (is_perfect_square(asdf))
      arr = {n, halfi - 2};
    else if (is_perfect_square(((long long int)halfi - 1) * (long long int)n))
      arr = {halfi - 2, n - 2};
    else
      arr = {2, halfi, n};
  }
  vector<int> ans = {};
  for (int i = 1; i < n + 1; i++) {
    if (find(arr.begin(), arr.end(), i) == arr.end()) ans.push_back(i);
  }
  cout << ans.size() << endl;
  for (int el = 0; el < ans.size(); el++) {
    cout << ans[el] << ' ';
  }
  cout << endl;
}
int main() {
  solve();
  return 0;
}

```