description: 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 
solution: #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;
  }
  