#include <bits/stdc++.h>
std::map<long long, int> mp;
int n, p[1000005], cnt, mindiv[1000005], vis[1000005], flag = 0;
long long val[1000005], pp[1000005], fac[1000005], pre[1000005];
std::mt19937 rd(*new int);
long long getrd(long long l, long long r) {
  std::uniform_int_distribution<long long> rand(l, r);
  return rand(rd);
}
void print() {
  int all = n;
  for (int i = 1; i <= n; i++)
    if (vis[i]) --all;
  printf("%d\n", all);
  for (int i = 1; i <= n; i++)
    if (!vis[i]) printf("%d ", i);
  puts("");
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) p[i] = 1000000000;
  cnt = 0;
  for (int i = 2; i <= n; i++) {
    if (!mindiv[i]) mindiv[i] = i, p[++cnt] = i;
    for (int j = 1; i * p[j] <= n && p[j] <= mindiv[i]; j++)
      mindiv[i * p[j]] = p[j];
  }
  for (int i = 1; i <= cnt; i++) pp[p[i]] = getrd(0, (1ll << 48) - 1);
  for (int i = 1; i <= n; i++) {
    int x = i;
    while (x > 1) val[i] = val[i] ^ pp[mindiv[x]], x = x / mindiv[x];
  }
  for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] ^ val[i];
  for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] ^ fac[i];
  long long gg = pre[n];
  if (gg == 0) return print(), 0;
  for (int i = 1; i <= n; i++)
    if ((gg ^ fac[i]) == 0) return vis[i] = 1, print(), 0;
  for (int i = 1; i <= n; i++) mp[gg ^ fac[i]] = i;
  for (int i = 1; i <= n; i++)
    if (mp[fac[i]]) return vis[i] = vis[mp[fac[i]]] = 1, print(), 0;
  int m = n / 4;
  if (n & 2)
    vis[2] = 1, vis[2 * m + 1] = 1;
  else
    vis[2 * m] = 1;
  if (n & 1) vis[n] = 1;
  print();
  return 0;
}

### 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>
std::map<long long, int> mp;
int n, p[1000005], cnt, mindiv[1000005], vis[1000005], flag = 0;
long long val[1000005], pp[1000005], fac[1000005], pre[1000005];
std::mt19937 rd(*new int);
long long getrd(long long l, long long r) {
  std::uniform_int_distribution<long long> rand(l, r);
  return rand(rd);
}
void print() {
  int all = n;
  for (int i = 1; i <= n; i++)
    if (vis[i]) --all;
  printf("%d\n", all);
  for (int i = 1; i <= n; i++)
    if (!vis[i]) printf("%d ", i);
  puts("");
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) p[i] = 1000000000;
  cnt = 0;
  for (int i = 2; i <= n; i++) {
    if (!mindiv[i]) mindiv[i] = i, p[++cnt] = i;
    for (int j = 1; i * p[j] <= n && p[j] <= mindiv[i]; j++)
      mindiv[i * p[j]] = p[j];
  }
  for (int i = 1; i <= cnt; i++) pp[p[i]] = getrd(0, (1ll << 48) - 1);
  for (int i = 1; i <= n; i++) {
    int x = i;
    while (x > 1) val[i] = val[i] ^ pp[mindiv[x]], x = x / mindiv[x];
  }
  for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] ^ val[i];
  for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] ^ fac[i];
  long long gg = pre[n];
  if (gg == 0) return print(), 0;
  for (int i = 1; i <= n; i++)
    if ((gg ^ fac[i]) == 0) return vis[i] = 1, print(), 0;
  for (int i = 1; i <= n; i++) mp[gg ^ fac[i]] = i;
  for (int i = 1; i <= n; i++)
    if (mp[fac[i]]) return vis[i] = vis[mp[fac[i]]] = 1, print(), 0;
  int m = n / 4;
  if (n & 2)
    vis[2] = 1, vis[2 * m + 1] = 1;
  else
    vis[2 * m] = 1;
  if (n & 1) vis[n] = 1;
  print();
  return 0;
}

```