let for_range s e step f =
  let rec loop i =
    if i >= e then ()
    else
      begin
        f i;loop (i + step)
      end
  in loop s;;

let a =
  let num = 1000000 in
  let p = Array.init (num+1) (fun x -> 1) in
  let rec loop i init =
    if i*i <= num then
      begin
        if p.(i) = 1 then
          begin
            for_range (5+(i*6)) num (i*6) (fun x -> p.(x) <- 0);
            for_range (7+(init-1)*6) num (i*6) (fun x -> p.(x) <- 0);
            for_range (7+((i+2)*6)) num ((i+2)*6) (fun x -> p.(x) <- 0);
            for_range (5+(init+1)*6) num ((i+2)*6) (fun x-> p.(x) <- 0);
          end;
        loop (i+6) (init+5)
      end
  in
  p.(0) <- 0; p.(1)<-(0);
  for_range 4 num 2 (fun x -> p.(x) <- 0);
  for_range 6 num 3 (fun x -> p.(x) <- 0);
  loop 5 4;
  for i = 1 to num-1 do
     p.(i) <- p.(i) + p.(i-1);
  done;
  let rec read () =
    try let n = read_int () in
        Printf.printf "%d\n" p.(n);
        read ()
    with End_of_file -> ()
  in read ();;