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: import java.io.PrintWriter;
  import java.util.*;
  
  public class Q {
      static int maxn = (int) 1e6 + 10;
      static long[] val = new long[maxn];
      static boolean[] compound = new boolean[maxn];
      static Random random;
      static Date date;
  
      public static void main(String[] args) {
          date = new Date();
          random = new Random(date.getTime() * 1000);
  
          Scanner scanner = new Scanner(System.in);
          int n = scanner.nextInt();
  
          for (int i = 2; i <= n; i++) {
              if (compound[i])
                  continue;
  
              while (val[i] == 0) {
                  val[i] = random.nextLong();
              }
  
              for (int j = 2 * i; j <= n; j += i) {
                  compound[j] = true;
                  int t = j;
                  int c = 0;
                  while (t % i == 0) {
                      t /= i;
                      c ^= 1;
                  }
  
                  if (c > 0) {
                      val[j] ^= val[i];
                  }
              }
          }
  
          HashSet<Long> hashSet = new HashSet<>();
          long x = 0;
          for (int i = 2; i <= n; i++) {
              val[i] ^= val[i - 1];
              x ^= val[i];
              hashSet.add(val[i]);
          }
  
          PrintWriter out = new PrintWriter(System.out);
  
          if (x == 0){
              out.println(n);
              for (int i = 1; i <= n; i++)
                  out.print(i + " ");
              out.println();
              out.close();
              return ;
          }
  
          int p1 = -1, p2 = -1;
          long tmp = 0;
          for (int i = 1; i <= n; i++){
              if (x == val[i]) {
                  p1 = i;
                  break;
              }
  
              if (hashSet.contains(val[i] ^ x)) {
                  p2 = i;
                  tmp = val[i] ^ x;
              }
          }
  
          if (p1 != -1){
              out.println(n-1);
              for (int i = 1; i <= n; i++){
                  if (i != p1)
                      out.print(i + " ");
              }
              out.println();
          }
          else if (p2 != -1){
              out.println(n-2);
              boolean flg = true;
              for (int i = 1; i <= n; i++){
                  if (i != p2){
                      if (val[i] == tmp){
                          if (flg) {
                              flg = false;
                          }
                          else {
                              out.print(i + " ");
                          }
                      }
                      else {
                          out.print(i + " ");
                      }
                  }
              }
              out.println();
          }
          else {
              out.println(n-3);
              for (int i = 1; i < n; i++){
                  if (i != 2 && i != n/2)
                      out.print(i + " ");
              }
              out.println();
          }
  
          out.close();
      }
  }
  