#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  long long n;
  cin >> n;
  auto is_sq = [&](long long x) {
    return (long long)sqrt(x) * (long long)sqrt(x) == x;
  };
  auto get_wont = [&]() -> vector<long long> {
    if (n % 4 == 0) return {n / 2};
    if (n == 1) return {};
    if (n % 4 == 1) return {n / 2, n};
    if (n % 4 == 2) {
      if (is_sq(n + 2)) return {n / 2 + 1};
      if (is_sq(n * (n / 2 + 1))) return {n / 2 - 2};
      return {n / 2, 2};
    }
    if (is_sq(n + 1)) return {n / 2 + 1, n};
    if (is_sq(2 * (n / 2) * (n / 2 - 1))) return {n / 2 - 2, n};
    if (is_sq((n / 2 - 1) * n)) return {n / 2 - 2, n - 2};
    return {2, n / 2, n};
  };
  auto wont = get_wont();
  cout << n - wont.size() << "\n";
  for (int i = 1; i <= n; i++)
    if (find(wont.begin(), wont.end(), i) == wont.end()) cout << i << " ";
  cout << "\n";
}

### 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;
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  long long n;
  cin >> n;
  auto is_sq = [&](long long x) {
    return (long long)sqrt(x) * (long long)sqrt(x) == x;
  };
  auto get_wont = [&]() -> vector<long long> {
    if (n % 4 == 0) return {n / 2};
    if (n == 1) return {};
    if (n % 4 == 1) return {n / 2, n};
    if (n % 4 == 2) {
      if (is_sq(n + 2)) return {n / 2 + 1};
      if (is_sq(n * (n / 2 + 1))) return {n / 2 - 2};
      return {n / 2, 2};
    }
    if (is_sq(n + 1)) return {n / 2 + 1, n};
    if (is_sq(2 * (n / 2) * (n / 2 - 1))) return {n / 2 - 2, n};
    if (is_sq((n / 2 - 1) * n)) return {n / 2 - 2, n - 2};
    return {2, n / 2, n};
  };
  auto wont = get_wont();
  cout << n - wont.size() << "\n";
  for (int i = 1; i <= n; i++)
    if (find(wont.begin(), wont.end(), i) == wont.end()) cout << i << " ";
  cout << "\n";
}

```