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: // package c1622;
  
  import java.io.File;
  import java.lang.invoke.MethodHandles;
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  import java.util.Random;
  import java.util.Scanner;
  
  //
  // Educational Codeforces Round 120 (Rated for Div. 2) 2021-12-27 06:35
  // F. Quadratic Set
  // https://codeforces.com/contest/1622/problem/F
  // time limit per test 4 seconds; memory limit per test 256 megabytes
  // public class Pseudo for 'Source should satisfy regex [^{}]*public\s+(final)?\s*class\s+(\w+).*'
  //
  // Let's call a set of positive integers a_1, a_2, ..., a_k if the product of the factorials of its
  // elements is a square of an integer, i.?e. \prod\limits_{i=1}^{k} a_i! = m^2, for some integer m.
  //
  // You are given a positive integer n.
  //
  // Your task is to find a 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.
  //
  // Example
  /*
  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
  */
  //
  
  // Based on https://codeforces.com/contest/1622/submission/140836054
  // The theory is: the size of the maximum quadratic subset of {1,2...,n} is either n, n-1, n-2, or n-3.
  // Further, when it is n-3, there is always a such subset without n.
  public class C1622F {
    static final int MOD = (int)1e9+7;
    static final Random RAND = new Random();
  
    static final int M = 1 << 30;
  
    static void solve(int n) {
      int[] p = new int[n+1];
      for (int i = 0; i <= n; i++) {
        p[i] = i;
      }
      for (int i = 2; i <= n; i++) {
        if (p[i] == i) {
          for (int j = i + i; j <= n; j += i) {
            if (p[j] == j) {
              p[j] = i;
            }
          }
        }
      }
      // System.out.format("  p: %s\n", Arrays.toString(p));
      long[] c = new long[n+1];
      for (int i = 2; i <= n; i++) {
        if (p[i] == i) {
          c[i] = (((long)RAND.nextInt(1 << 30)) << 30) + RAND.nextInt(1 << 30);
        }
      }
      // System.out.format("  c: %s\n", Arrays.toString(c));
  
      long[] num = new long[n+1];
      num[1] = 0;
      for (int i = 2; i <= n; i++) {
        num[i] = num[i / p[i]] ^ c[p[i]];
      }
      // System.out.format("num: %s\n", Arrays.toString(num));
  
      long[] f = new long[n+1];
      f[1] = 0;
      for (int i = 2; i <= n; i++) {
        f[i] = f[i - 1] ^ num[i];
      }
      // System.out.format("  f: %s\n", Arrays.toString(f));
  
      long all = 0;
      for (int i = 1; i <= n; i++) {
        all ^= f[i];
      }
      // System.out.format("all: %d\n", all);
      if (all == 0) {
        print(n, new int[] {});
        return;
      }
  
      for (int i = 1; i <= n; i++) {
        if (all == f[i]) {
          print(n, new int[] {i});
          return;
        }
      }
  
  
      Map<Long, List<Integer>> pm = new HashMap<>();
      for (int i = 1; i <= n; i++) {
        pm.computeIfAbsent(f[i],  x->new ArrayList<>()).add(i);
      }
      for (int i = 1; i <= n; i++) {
        long need = all ^ f[i];
        if (pm.containsKey(need)) {
          print(n, new int[] {i, pm.get(need).get(0)});
          return;
        }
        // int idx = Arrays.binarySearch(ps, new long[] {need, -1}, new Comparator<long[]>() {});
        // auto it = lower_bound(ps.begin(), ps.end(), make_pair(need, -1));
      }
      myAssert(n % 2 == 1);
      all ^= f[n];
      for (int i = 1; i <= n - 1; i++) {
        long need = all ^ f[i];
        if (pm.containsKey(need)) {
          print(n, new int[] {i, pm.get(need).get(0), n});
          return;
        }
      }
  
      List<long[]> ps = new ArrayList<>();
      // long[][] ps = new long[n][2];
      // Arrays.sort(ps, (x,y) -> Long.compare(x[0], y[0]));
      for (int i = 1; i <= n; i++) {
        ps.add(new long[] {f[i], i});
      }
      Collections.sort(ps, (x,y) -> x[0] != y[0] ? Long.compare(x[0],y[0]) : Long.compare(x[1], y[1]));
      for (int i = 1; i <= n; i++) {
        long need = all ^ f[i];
        long[] key = new long[] {need, -1};
        int k = Collections.binarySearch(ps, key,
            (x,y) -> x[0] != y[0] ? Long.compare(x[0],y[0]) : Long.compare(x[1], y[1]));
        // System.out.format("  i: %d need: %d k:%d\n", i, need, k);
        if (k < 0) {
          k = -(k+1);
        }
        if (k < ps.size() && ps.get(k)[0] == need) {
          print(n, new int[] {i, (int) ps.get(k)[1]});
          return;
        }
        // int idx = Arrays.binarySearch(ps, new long[] {need, -1}, new Comparator<long[]>() {});
        // auto it = lower_bound(ps.begin(), ps.end(), make_pair(need, -1));
      }
      myAssert(n % 2 == 1);
      all ^= f[n];
      for (int i = 1; i <= n - 1; i++) {
        long need = all ^ f[i];
        long[] key = new long[] {need, -1};
        int k = Collections.binarySearch(ps, key,
            (x,y) -> x[0] != y[0] ? Long.compare(x[0],y[0]) : Long.compare(x[1], y[1]));
        if (k < 0) {
          k = -(k+1);
        }
        if (k < ps.size() && ps.get(k)[0] == need && ps.get(k)[1] < n) {
          print(n, new int[] {i, (int) ps.get(k)[1], n});
          return;
        }
      }
      myAssert(false);
    }
  
    // Due to the potential large size of 1000000
    // Directly print every 100 numbers
    static void print(int n, int[] remove) {
      boolean[] exclude = new boolean[n+1];
      int m = n;
      for (int v : remove) {
        exclude[v] = true;
        m--;
      }
      System.out.println(m);
      StringBuilder sb = new StringBuilder();
      for (int i = 1; i <= n; i++) {
        if (!exclude[i]) {
          sb.append(i);
          sb.append(' ');
          if (sb.length() > 1000) {
            System.out.println(sb.toString());
            sb.setLength(0);
          }
        }
      }
      System.out.println(sb.toString());
    }
  
    static void myAssert(boolean cond) {
      if (!cond) {
        throw new RuntimeException("Unexpected");
      }
    }
  
    static String trace(int[] a) {
      StringBuilder sb = new StringBuilder(7 * a.length);
      for (int v : a) {
       if (sb.length() > 0) {
         sb.append(' ');
       }
       sb.append(v);
      }
      return sb.toString();
    }
  
    static void doTest() {
      long t0 = System.currentTimeMillis();
      int n = 1000000;
      solve(n);
      System.out.format("%d msec\n", System.currentTimeMillis() - t0);
      System.exit(0);
    }
  
    public static void main(String[] args) {
      // doTest();
      Scanner in = getInputScanner();
      int n = in.nextInt();
      solve(n);
      in.close();
    }
  
    static Scanner getInputScanner() {
      try {
        final String USERDIR = System.getProperty("user.dir");
        final String CNAME = MethodHandles.lookup().lookupClass().getSimpleName();
        final File fin = new File(USERDIR + "/io/c" + CNAME.substring(1,5) + "/" + CNAME + ".in");
        return fin.exists() ? new Scanner(fin) : new Scanner(System.in);
      } catch (Exception e) {
        return new Scanner(System.in);
      }
    }
  }
  