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 ll = long long;
  using ld = long double;
  namespace GTI {
  char gc(void) {
    const int S = 1 << 16;
    static char buf[S], *s = buf, *t = buf;
    if (s == t) t = buf + fread(s = buf, 1, S, stdin);
    if (s == t) return EOF;
    return *s++;
  }
  ll gti(void) {
    ll a = 0, b = 1, c = gc();
    for (; !isdigit(c); c = gc()) b ^= (c == '-');
    for (; isdigit(c); c = gc()) a = a * 10 + c - '0';
    return b ? a : -a;
  }
  int gts(char *s) {
    int len = 0, c = gc();
    for (; isspace(c); c = gc())
      ;
    for (; c != EOF && !isspace(c); c = gc()) s[len++] = c;
    s[len] = 0;
    return len;
  }
  int gtl(char *s) {
    int len = 0, c = gc();
    for (; isspace(c); c = gc())
      ;
    for (; c != EOF && c != '\n'; c = gc()) s[len++] = c;
    s[len] = 0;
    return len;
  }
  }  // namespace GTI
  using GTI::gti;
  using GTI::gtl;
  using GTI::gts;
  using RandType = std::mt19937_64;
  RandType init_rand(void) {
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    RandType rand_num(seed);
    return rand_num;
  }
  RandType randx = init_rand();
  using ull = unsigned long long;
  const int N = 1e6 + 500;
  bool vis[N];
  int pri[N], pcnt, dv[N];
  ull key[N], tag[N], pre[N];
  std::unordered_map<ull, int> id;
  void getpri(int n) {
    for (int i = 2; i <= n; i++) {
      if (!vis[i]) ++pcnt, pri[pcnt] = i, key[pcnt] = randx(), dv[i] = pcnt;
      for (int j = 1; j <= pcnt && 1ll * i * pri[j] <= n; j++) {
        vis[i * pri[j]] = true;
        dv[i * pri[j]] = j;
        if (i % pri[j] == 0) break;
      }
    }
    for (int i = 2; i <= n; i++) {
      int v = i;
      while (v > 1) tag[i] ^= key[dv[v]], v /= pri[dv[v]];
    }
    for (int i = 1; i <= n; i++) tag[i] ^= tag[i - 1], id[tag[i]] = i;
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] ^ tag[i];
  }
  int ans = 0, ansp[N];
  void calc(int n) {
    if (n < ans) return;
    ull now = pre[n];
    if (now == 0) {
      if (n > ans) {
        ans = n;
        for (int i = 1; i <= n; i++) ansp[i] = i;
      }
      return;
    }
    for (int i = 2; i < n; i++)
      if ((now ^ tag[i]) == 0) {
        if (n - 1 > ans) {
          ans = 0;
          for (int d = 1; d <= n; d++)
            if (d != i) ansp[++ans] = d;
        }
        return;
      }
    for (int i = 2; i < n; i++)
      if (id.count(now ^ tag[i])) {
        int j = id[now ^ tag[i]];
        if (j <= n) {
          if (n - 2 > ans) {
            ans = 0;
            for (int d = 1; d <= n; d++)
              if (d != i && d != j) ansp[++ans] = d;
          }
          return;
        }
      }
  }
  int main(void) {
    int n = gti();
    getpri(n);
    for (int i = n; i >= 1; i--) calc(i);
    printf("%d\n", ans);
    for (int i = 1; i <= ans; i++) printf("%d%c", ansp[i], " \n"[i == ans]);
    return 0;
  }
  