open List
let m3_cycle_length = 30
let m3_primes = [5; 3; 2]
let m3_cycle = [6; 4; 2; 4; 2; 4; 6; 2]

let wheel_fact limit =
  let slimit = limit in
  let rec wheel_loop limit n nxt result =
  let get_m3_cycle n =
      nth m3_cycle (n mod ((length m3_cycle)))
  in
  if nxt > limit then tl (sort (fun x y -> if x == 0 then 0
                            else if x > y then 1
                            else -1) (rev (result @ m3_primes)))
  else wheel_loop limit (n + 1) (nxt + (get_m3_cycle n)) (nxt :: result)
  in wheel_loop slimit 0 1 []

let sieve xs =
  let rec sieve_loop xs ys =
    let comp_filter n xs = 
      List.filter (fun x -> x mod n != 0 && n != x) xs 
    in 
    match xs with
      [] -> ys
    | x :: xs -> sieve_loop (comp_filter x xs) (x :: ys)
  in
  sieve_loop xs []

let split xs n =
  let rec split_loop xs n ys =
    if n <= 0 then (ys, xs)
    else split_loop (tl xs) (n - 1) (hd xs :: ys)
  in
  split_loop xs n []

let uniq xs =
  let rec uniq_loop xs ys =
    match xs with
      [] -> ys
    | x :: xs -> uniq_loop (filter (fun (l1, l2) -> l1 != fst x && l2 != snd x) xs) (x :: ys)
  in uniq_loop xs []

let goldbach n =
  let rec gold_loop xs ys zs = 
    let rec bach_loop x ys =
      match ys with 
        [] -> (0, 0)
      | y :: ys -> if n == y + x then 
                      if x < y then (x, y) else (y, x)
                   else bach_loop x ys
    in
    match xs with
      [] -> zs
    | x :: xs -> gold_loop xs ys ((bach_loop x ys) :: zs)
  in
  let sieved = sieve (wheel_fact n) in
  let (sieved1, _) = split sieved ((length sieved) / 2) in
  uniq(filter (fun (x, y) -> x != 0 && y != 0) (gold_loop sieved1 sieved []))

let goldbach_length n = length (goldbach n)

let () =
  let rec echo_sub () =
    print_int (goldbach_length(int_of_string(read_line ())));
    print_newline ();
    echo_sub ()
  in
    try echo_sub () with End_of_file -> ()