#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using pii = pair<int, int>;
using vec = vector<int>;
using veg = vector<pii>;
using ull = unsigned long long;
template <typename T>
T read() {
  T x = 0;
  bool f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}
template <typename T>
void chkmax(T &x, const T &y) {
  x = x > y ? x : y;
}
template <typename T>
void chkmin(T &x, const T &y) {
  x = x < y ? x : y;
}
const int N = 1e6 + 10;
mt19937_64 rnd(time(NULL));
ull pri[N], all, b[N];
int n;
map<ull, int> s;
bool vis[N];
void output(const vec &ban) {
  for (int i = (1); i <= (n); i++) vis[i] = true;
  for (auto v : ban) vis[v] = false;
  vec pot;
  for (int i = (1); i <= (n); i++)
    if (vis[i]) pot.emplace_back(i);
  printf("%lu\n", pot.size());
  for (auto v : pot) printf("%d ", v);
  puts("");
  exit(0);
}
int main() {
  n = read<int>();
  for (int i = (2); i <= (n); i++) {
    pri[i] = rnd();
    int x = i;
    for (int j = (2); j <= (x); j++) {
      if (j * j > x) break;
      while (x % j == 0) b[i] ^= pri[j], x /= j;
    }
    if (x > 1) b[i] ^= pri[x];
    b[i] ^= b[i - 1];
    all ^= b[i];
  }
  if (all == 0) output({});
  for (int i = (2); i <= (n); i++) s[b[i]] = i;
  if (s.count(all)) output({s[all]});
  for (int i = (2); i <= (n); i++)
    if (s.count(all ^ b[i])) output({i, s[all ^ b[i]]});
  all ^= b[n];
  for (int i = (2); i <= (n - 1); i++)
    if (s.count(all ^ b[i])) output({i, s[all ^ b[i]], n});
  assert(0);
  return 0;
}

### Prompt

In CPP, your task is to solve 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;
using ll = long long;
using db = double;
using pii = pair<int, int>;
using vec = vector<int>;
using veg = vector<pii>;
using ull = unsigned long long;
template <typename T>
T read() {
  T x = 0;
  bool f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}
template <typename T>
void chkmax(T &x, const T &y) {
  x = x > y ? x : y;
}
template <typename T>
void chkmin(T &x, const T &y) {
  x = x < y ? x : y;
}
const int N = 1e6 + 10;
mt19937_64 rnd(time(NULL));
ull pri[N], all, b[N];
int n;
map<ull, int> s;
bool vis[N];
void output(const vec &ban) {
  for (int i = (1); i <= (n); i++) vis[i] = true;
  for (auto v : ban) vis[v] = false;
  vec pot;
  for (int i = (1); i <= (n); i++)
    if (vis[i]) pot.emplace_back(i);
  printf("%lu\n", pot.size());
  for (auto v : pot) printf("%d ", v);
  puts("");
  exit(0);
}
int main() {
  n = read<int>();
  for (int i = (2); i <= (n); i++) {
    pri[i] = rnd();
    int x = i;
    for (int j = (2); j <= (x); j++) {
      if (j * j > x) break;
      while (x % j == 0) b[i] ^= pri[j], x /= j;
    }
    if (x > 1) b[i] ^= pri[x];
    b[i] ^= b[i - 1];
    all ^= b[i];
  }
  if (all == 0) output({});
  for (int i = (2); i <= (n); i++) s[b[i]] = i;
  if (s.count(all)) output({s[all]});
  for (int i = (2); i <= (n); i++)
    if (s.count(all ^ b[i])) output({i, s[all ^ b[i]]});
  all ^= b[n];
  for (int i = (2); i <= (n - 1); i++)
    if (s.count(all ^ b[i])) output({i, s[all ^ b[i]], n});
  assert(0);
  return 0;
}

```