#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T &t) {
  t = 0;
  char ch = getchar();
  int f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  do {
    (t *= 10) += ch - '0';
    ch = getchar();
  } while ('0' <= ch && ch <= '9');
  t *= f;
}
template <typename T>
void write(T t) {
  if (t < 0) {
    putchar('-');
    write(-t);
    return;
  }
  if (t > 9) write(t / 10);
  putchar('0' + t % 10);
}
template <typename T>
void writeln(T t) {
  write(t);
  puts("");
}
const int maxn = (1e6) + 10;
int n;
unsigned long long Rand[maxn], pre[maxn];
bool vis[maxn];
int tot, prime[maxn];
unsigned long long GET() {
  unsigned long long res = 0;
  for (int i = 0; i < 64; i++)
    if (rand() & 1) res |= (unsigned long long)1 << i;
  return res;
}
int mx;
map<unsigned long long, int> M;
void solve(int n) {
  unsigned long long all = 0;
  for (int i = 1; i <= n; i++) all ^= Rand[i];
  for (int i = 1; i <= n; i++) M[Rand[i] ^ all] = i;
  for (int i = 1; i <= n; i++)
    if (M[Rand[i]]) {
      int j = M[Rand[i]];
      printf("%d\n", n - 2);
      for (int k = 1; k <= n; k++)
        if (i != k && j != k) printf("%d ", k);
      puts("");
      exit(0);
    }
}
int main() {
  for (int i = 2; i < maxn; i++) {
    if (!vis[i]) {
      prime[++tot] = i, Rand[i] = GET();
    }
    for (int j = 1; j <= tot; j++) {
      if (prime[j] * i >= maxn) break;
      vis[i * prime[j]] = 1;
      Rand[i * prime[j]] = (Rand[i] ^ Rand[prime[j]]);
      if (i % prime[j] == 0) break;
    }
  }
  for (int i = 2; i < maxn; i++) Rand[i] ^= Rand[i - 1];
  read(n);
  unsigned long long all = 0;
  for (int i = 1; i <= n; i++) all ^= Rand[i];
  if (!all) {
    printf("%d\n", n);
    for (int i = 1; i <= n; i++) printf("%d ", i);
    puts("");
    return 0;
  }
  for (int i = 1; i <= n; i++)
    if (Rand[i] == all) {
      printf("%d\n", n - 1);
      for (int j = 1; j <= n; j++)
        if (i != j) printf("%d ", j);
      puts("");
      return 0;
    }
  solve(n);
  solve(n - 1);
  return 0;
}

### Prompt

Your challenge is to write 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;
template <typename T>
void read(T &t) {
  t = 0;
  char ch = getchar();
  int f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  do {
    (t *= 10) += ch - '0';
    ch = getchar();
  } while ('0' <= ch && ch <= '9');
  t *= f;
}
template <typename T>
void write(T t) {
  if (t < 0) {
    putchar('-');
    write(-t);
    return;
  }
  if (t > 9) write(t / 10);
  putchar('0' + t % 10);
}
template <typename T>
void writeln(T t) {
  write(t);
  puts("");
}
const int maxn = (1e6) + 10;
int n;
unsigned long long Rand[maxn], pre[maxn];
bool vis[maxn];
int tot, prime[maxn];
unsigned long long GET() {
  unsigned long long res = 0;
  for (int i = 0; i < 64; i++)
    if (rand() & 1) res |= (unsigned long long)1 << i;
  return res;
}
int mx;
map<unsigned long long, int> M;
void solve(int n) {
  unsigned long long all = 0;
  for (int i = 1; i <= n; i++) all ^= Rand[i];
  for (int i = 1; i <= n; i++) M[Rand[i] ^ all] = i;
  for (int i = 1; i <= n; i++)
    if (M[Rand[i]]) {
      int j = M[Rand[i]];
      printf("%d\n", n - 2);
      for (int k = 1; k <= n; k++)
        if (i != k && j != k) printf("%d ", k);
      puts("");
      exit(0);
    }
}
int main() {
  for (int i = 2; i < maxn; i++) {
    if (!vis[i]) {
      prime[++tot] = i, Rand[i] = GET();
    }
    for (int j = 1; j <= tot; j++) {
      if (prime[j] * i >= maxn) break;
      vis[i * prime[j]] = 1;
      Rand[i * prime[j]] = (Rand[i] ^ Rand[prime[j]]);
      if (i % prime[j] == 0) break;
    }
  }
  for (int i = 2; i < maxn; i++) Rand[i] ^= Rand[i - 1];
  read(n);
  unsigned long long all = 0;
  for (int i = 1; i <= n; i++) all ^= Rand[i];
  if (!all) {
    printf("%d\n", n);
    for (int i = 1; i <= n; i++) printf("%d ", i);
    puts("");
    return 0;
  }
  for (int i = 1; i <= n; i++)
    if (Rand[i] == all) {
      printf("%d\n", n - 1);
      for (int j = 1; j <= n; j++)
        if (i != j) printf("%d ", j);
      puts("");
      return 0;
    }
  solve(n);
  solve(n - 1);
  return 0;
}

```