#include <bits/stdc++.h>
using namespace std;
namespace my_rand {
uint64_t rng() {
  static uint64_t x_ =
      uint64_t(chrono::duration_cast<chrono::nanoseconds>(
                   chrono::high_resolution_clock::now().time_since_epoch())
                   .count()) *
      10150724397891781847ULL;
  x_ ^= x_ << 7;
  return x_ ^= x_ >> 9;
}
int64_t randint(int64_t l, int64_t r) {
  assert(l < r);
  return l + rng() % (r - l);
}
vector<int64_t> randset(int64_t l, int64_t r, int64_t n) {
  assert(l <= r && n <= r - l);
  unordered_set<int64_t> s;
  for (int64_t i = n; i; --i) {
    int64_t m = randint(l, r + 1 - i);
    if (s.find(m) != s.end()) m = r - i;
    s.insert(m);
  }
  vector<int64_t> ret;
  for (auto& x : s) ret.push_back(x);
  return ret;
}
double rnd() {
  union raw_cast {
    double t;
    uint64_t u;
  };
  constexpr uint64_t p = uint64_t(1023 - 64) << 52;
  return rng() * ((raw_cast*)(&p))->t;
}
template <typename T>
void randshf(vector<T>& v) {
  int n = v.size();
  for (int loop = 0; loop < 2; loop++)
    for (int i = 0; i < n; i++) swap(v[i], v[randint(0, n)]);
}
}  // namespace my_rand
using my_rand::randint;
using my_rand::randset;
using my_rand::randshf;
using my_rand::rnd;
using my_rand::rng;
template <int SZ>
struct Sieve {
  int spf[SZ];
  Sieve() {
    spf[1] = 1;
    for (int i = 2; i < SZ; i++) spf[i] = i;
    for (int i = 4; i < SZ; i += 2) spf[i] = 2;
    for (int i = 3; i * i < SZ; i++)
      if (spf[i] == i)
        for (int j = i * i; j < SZ; j += i)
          if (spf[j] == j) spf[j] = i;
  }
  std::vector<std::pair<int, int>> factor(int x) {
    std::vector<std::pair<int, int>> ret;
    while (x != 1) {
      if ((int)ret.size() == 0)
        ret.emplace_back(spf[x], 1);
      else {
        if (ret.back().first == spf[x])
          ret.back().second++;
        else
          ret.emplace_back(spf[x], 1);
      }
      x /= spf[x];
    }
    return ret;
  }
};
vector<int> check3(int n) {
  if (n % 4 == 0 || n % 4 == 1) {
    if (n % 4 == 1) {
      --n;
    }
    vector<int> ret;
    for (int i = 1; i <= n; ++i) {
      if (i == n / 2) {
        continue;
      }
      ret.push_back(i);
    }
    return ret;
  } else {
    if (n % 4 == 3) {
      --n;
    }
    vector<int> ret;
    for (int i = 1; i <= n; ++i) {
      if (i == 2 || i == n / 2) {
        continue;
      }
      ret.push_back(i);
    }
    return ret;
  }
}
vector<int> check2(int n) {
  const int N = 1e6 + 5;
  const long long B = 1e18;
  Sieve<N> sieve;
  vector<long long> random(n + 1);
  vector<long long> hashes(n + 1);
  for (int i = 1; i <= n; ++i) {
    random[i] = randint(B, 9 * B);
    auto f = sieve.factor(i);
    for (auto [p, e] : f) {
      if (e & 1) {
        hashes[i] ^= random[p];
      }
    }
    hashes[i] ^= hashes[i - 1];
  }
  long long all = 0;
  for (long long x : hashes) {
    all ^= x;
  }
  multiset<long long> in;
  for (long long x : hashes) {
    in.insert(x);
  }
  for (int i = 1; i <= n; ++i) {
    in.erase(in.find(hashes[i]));
    if (in.count(hashes[i] ^ all)) {
      for (int j = 1; j <= n; ++j) {
        if (i != j && hashes[j] == (hashes[i] ^ all)) {
          vector<int> ret;
          for (int k = 1; k <= n; ++k) {
            if (k == i || k == j) {
              continue;
            }
            ret.push_back(k);
          }
          return ret;
        }
      }
    }
    in.insert(hashes[i]);
  }
  return {};
}
vector<int> check1(int n) {
  const int N = 1e6 + 5;
  const long long B = 1e18;
  Sieve<N> sieve;
  vector<long long> random(n + 1);
  vector<long long> hashes(n + 1);
  for (int i = 1; i <= n; ++i) {
    random[i] = randint(B, 9 * B);
    auto f = sieve.factor(i);
    for (auto [p, e] : f) {
      if (e & 1) {
        hashes[i] ^= random[p];
      }
    }
    hashes[i] ^= hashes[i - 1];
  }
  long long all = 0;
  for (long long x : hashes) {
    all ^= x;
  }
  for (int i = 1; i <= n; ++i) {
    if (hashes[i] == all) {
      vector<int> ret;
      for (int j = 1; j <= n; ++j) {
        if (i == j) {
          continue;
        }
        ret.push_back(j);
      }
      return ret;
    }
  }
  return {};
}
vector<int> check0(int n) {
  const int N = 1e6 + 5;
  const long long B = 1e18;
  Sieve<N> sieve;
  vector<long long> random(n + 1);
  vector<long long> hashes(n + 1);
  for (int i = 1; i <= n; ++i) {
    random[i] = randint(B, 9 * B);
    auto f = sieve.factor(i);
    for (auto [p, e] : f) {
      if (e & 1) {
        hashes[i] ^= random[p];
      }
    }
    hashes[i] ^= hashes[i - 1];
  }
  long long all = 0;
  for (long long x : hashes) {
    all ^= x;
  }
  if (all == 0) {
    vector<int> ret;
    for (int i = 1; i <= n; ++i) {
      ret.push_back(i);
    }
    return ret;
  }
  return {};
}
void finish(vector<int> v) {
  cout << (int)v.size() << '\n';
  for (int x : v) {
    cout << x << ' ';
  }
  cout << '\n';
  exit(0);
}
int main() {
  int n;
  cin >> n;
  auto ans = check0(n);
  if (!ans.empty()) {
    finish(ans);
  }
  ans = check1(n);
  if (!ans.empty()) {
    finish(ans);
  }
  ans = check2(n);
  if (!ans.empty()) {
    finish(ans);
  }
  ans = check3(n);
  if (!ans.empty()) {
    finish(ans);
  }
  return 0;
}

### Prompt

Develop a solution in CPP 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;
namespace my_rand {
uint64_t rng() {
  static uint64_t x_ =
      uint64_t(chrono::duration_cast<chrono::nanoseconds>(
                   chrono::high_resolution_clock::now().time_since_epoch())
                   .count()) *
      10150724397891781847ULL;
  x_ ^= x_ << 7;
  return x_ ^= x_ >> 9;
}
int64_t randint(int64_t l, int64_t r) {
  assert(l < r);
  return l + rng() % (r - l);
}
vector<int64_t> randset(int64_t l, int64_t r, int64_t n) {
  assert(l <= r && n <= r - l);
  unordered_set<int64_t> s;
  for (int64_t i = n; i; --i) {
    int64_t m = randint(l, r + 1 - i);
    if (s.find(m) != s.end()) m = r - i;
    s.insert(m);
  }
  vector<int64_t> ret;
  for (auto& x : s) ret.push_back(x);
  return ret;
}
double rnd() {
  union raw_cast {
    double t;
    uint64_t u;
  };
  constexpr uint64_t p = uint64_t(1023 - 64) << 52;
  return rng() * ((raw_cast*)(&p))->t;
}
template <typename T>
void randshf(vector<T>& v) {
  int n = v.size();
  for (int loop = 0; loop < 2; loop++)
    for (int i = 0; i < n; i++) swap(v[i], v[randint(0, n)]);
}
}  // namespace my_rand
using my_rand::randint;
using my_rand::randset;
using my_rand::randshf;
using my_rand::rnd;
using my_rand::rng;
template <int SZ>
struct Sieve {
  int spf[SZ];
  Sieve() {
    spf[1] = 1;
    for (int i = 2; i < SZ; i++) spf[i] = i;
    for (int i = 4; i < SZ; i += 2) spf[i] = 2;
    for (int i = 3; i * i < SZ; i++)
      if (spf[i] == i)
        for (int j = i * i; j < SZ; j += i)
          if (spf[j] == j) spf[j] = i;
  }
  std::vector<std::pair<int, int>> factor(int x) {
    std::vector<std::pair<int, int>> ret;
    while (x != 1) {
      if ((int)ret.size() == 0)
        ret.emplace_back(spf[x], 1);
      else {
        if (ret.back().first == spf[x])
          ret.back().second++;
        else
          ret.emplace_back(spf[x], 1);
      }
      x /= spf[x];
    }
    return ret;
  }
};
vector<int> check3(int n) {
  if (n % 4 == 0 || n % 4 == 1) {
    if (n % 4 == 1) {
      --n;
    }
    vector<int> ret;
    for (int i = 1; i <= n; ++i) {
      if (i == n / 2) {
        continue;
      }
      ret.push_back(i);
    }
    return ret;
  } else {
    if (n % 4 == 3) {
      --n;
    }
    vector<int> ret;
    for (int i = 1; i <= n; ++i) {
      if (i == 2 || i == n / 2) {
        continue;
      }
      ret.push_back(i);
    }
    return ret;
  }
}
vector<int> check2(int n) {
  const int N = 1e6 + 5;
  const long long B = 1e18;
  Sieve<N> sieve;
  vector<long long> random(n + 1);
  vector<long long> hashes(n + 1);
  for (int i = 1; i <= n; ++i) {
    random[i] = randint(B, 9 * B);
    auto f = sieve.factor(i);
    for (auto [p, e] : f) {
      if (e & 1) {
        hashes[i] ^= random[p];
      }
    }
    hashes[i] ^= hashes[i - 1];
  }
  long long all = 0;
  for (long long x : hashes) {
    all ^= x;
  }
  multiset<long long> in;
  for (long long x : hashes) {
    in.insert(x);
  }
  for (int i = 1; i <= n; ++i) {
    in.erase(in.find(hashes[i]));
    if (in.count(hashes[i] ^ all)) {
      for (int j = 1; j <= n; ++j) {
        if (i != j && hashes[j] == (hashes[i] ^ all)) {
          vector<int> ret;
          for (int k = 1; k <= n; ++k) {
            if (k == i || k == j) {
              continue;
            }
            ret.push_back(k);
          }
          return ret;
        }
      }
    }
    in.insert(hashes[i]);
  }
  return {};
}
vector<int> check1(int n) {
  const int N = 1e6 + 5;
  const long long B = 1e18;
  Sieve<N> sieve;
  vector<long long> random(n + 1);
  vector<long long> hashes(n + 1);
  for (int i = 1; i <= n; ++i) {
    random[i] = randint(B, 9 * B);
    auto f = sieve.factor(i);
    for (auto [p, e] : f) {
      if (e & 1) {
        hashes[i] ^= random[p];
      }
    }
    hashes[i] ^= hashes[i - 1];
  }
  long long all = 0;
  for (long long x : hashes) {
    all ^= x;
  }
  for (int i = 1; i <= n; ++i) {
    if (hashes[i] == all) {
      vector<int> ret;
      for (int j = 1; j <= n; ++j) {
        if (i == j) {
          continue;
        }
        ret.push_back(j);
      }
      return ret;
    }
  }
  return {};
}
vector<int> check0(int n) {
  const int N = 1e6 + 5;
  const long long B = 1e18;
  Sieve<N> sieve;
  vector<long long> random(n + 1);
  vector<long long> hashes(n + 1);
  for (int i = 1; i <= n; ++i) {
    random[i] = randint(B, 9 * B);
    auto f = sieve.factor(i);
    for (auto [p, e] : f) {
      if (e & 1) {
        hashes[i] ^= random[p];
      }
    }
    hashes[i] ^= hashes[i - 1];
  }
  long long all = 0;
  for (long long x : hashes) {
    all ^= x;
  }
  if (all == 0) {
    vector<int> ret;
    for (int i = 1; i <= n; ++i) {
      ret.push_back(i);
    }
    return ret;
  }
  return {};
}
void finish(vector<int> v) {
  cout << (int)v.size() << '\n';
  for (int x : v) {
    cout << x << ' ';
  }
  cout << '\n';
  exit(0);
}
int main() {
  int n;
  cin >> n;
  auto ans = check0(n);
  if (!ans.empty()) {
    finish(ans);
  }
  ans = check1(n);
  if (!ans.empty()) {
    finish(ans);
  }
  ans = check2(n);
  if (!ans.empty()) {
    finish(ans);
  }
  ans = check3(n);
  if (!ans.empty()) {
    finish(ans);
  }
  return 0;
}

```