open Batteries
open Printf

let ($) g f x = g (f x)

module MyList = struct
  include List
  let foldl = fold_left
  let foldli = fold_lefti
  let foldr = fold_right
  let foldri = fold_righti
  
  let flatmap = concat_map

  let zipf = map2
  let zipfi = map2i
end

module L = MyList

let swap = Tuple2.swap

let atoi = int_of_string
let itoa = string_of_int
let atof = float_of_string
let ftoa = string_of_float
let ctoi = int_of_char
let itoc = char_of_int

let ctos = String.of_char
let stocl = String.to_list
let cltos = String.of_list

module MyString = struct
  include String

  let map_to_list f s = L.map f (stocl s)
  let mapi_to_list f s = L.map f (stocl s)

  let zipf f a b = L.zipf f (stocl a) (stocl b)
  let zipfi f a b = L.zipfi f (stocl a) (stocl b)

  let mkstr f sep ls =
    L.foldl (fun acc x -> acc ^ sep ^ (f x)) (f @@ L.hd ls) (List.tl ls)
end

module S = MyString

let spoc = S.split_on_char
let spsp s = spoc ' ' s

module MySet = struct
  include Set

  let fold' f s z = fold f z s
end

module St = MySet

module MyMap = struct
  include Map

  let apply = find
  let apply_or = find_default
end

module Mp = MyMap


let rds () = read_line ()

let rdi () = atoi @@ rds ()

let rdhs () = spsp @@ rds ()
let rdhi () = rdhs () |> L.map atoi

let rds2 () = match rdhs () with
  | a::b::_ -> (a, b)
  | _ -> ("", "")

let rdi2 () = match rdhi () with
  | a::b::_ -> (a, b)
  | _ -> (0, 0)

let rdi3 () = match rdhi () with
| a::b::c::_ -> (a, b, c)
| _ -> (0, 0, 0)

let rdi4 () = match rdhi () with
| a::b::c::d::_ -> (a, b, c, d)
| _ -> (0, 0, 0, 0)

let rdi5 () = match rdhi () with
| a::b::c::d::e::_ -> (a, b, c, d, e)
| _ -> (0, 0, 0, 0, 0)

let rdv n rdf =
  let rec rdv' n =
    if n <= 0 then []
    else (
      let s = rdf () in
      s::(rdv' (n - 1))
    )
  in rdv' n

let rdvi n = rdv n rdi
let rdvi2 n = rdv n rdi2
let rdvi3 n = rdv n rdi3
let rdvi4 n = rdv n rdi4

let puts s = print_endline s
let putyn b = puts (if b then "Yes" else "No")
let puti i = puts @@ itoa i

let set_power ls =
  let rec set_power' ls pls =
    match ls with
    | [] -> pls
    | hd::tl -> set_power' tl (L.flatmap (fun p -> [p; hd::p]) pls)
  in set_power' ls [[]]


let rdhf () = rdhs () |> L.map atof
let rdf4 () = match rdhf () with
| a::b::c::d::_ -> (a, b, c, d)
| _ -> (0., 0., 0., 0.)


module Graph = struct

  type 'a t = { nb : (int, int St.t) Mp.t; vdt : (int, 'a) Mp.t }

  let nothing = { nb = Mp.empty; vdt = Mp.empty }

  let add_edge (e : int * int) g =
    let (v1, v2) = e in
    let nbvs = g.nb |> Mp.apply_or St.empty v1 in
    let nb1 = g.nb |> Mp.add v1 (nbvs |> St.add v2) in
    { g with nb = nb1 }

  let add_uedge e g =
    add_edge e (add_edge (swap e) g)

  let from_edges es =
    es |> L.foldl (fun g e -> add_edge e g) nothing

  let from_uedges es =
    es |> L.foldl (fun g e -> add_uedge e g) nothing


end

module G = Graph


let _ =
  let n = rdi () in
  let mx = 1000000 in
  let primes_to_1000 = [
  2;3;5;7;11;13;17;19;23;29;31;37;41;43;47;53;59;61;67;71;73;79;83;89;97;101;
  103;107;109;113;127;131;137;139;149;151;157;163;167;173;179;181;191;193;197;
  199;211;223;227;229;233;239;241;251;257;263;269;271;277;281;283;293;307;311;
  313;317;331;337;347;349;353;359;367;373;379;383;389;397;401;409;419;421;431;
  433;439;443;449;457;461;463;467;479;487;491;499;503;509;521;523;541;547;557;
  563;569;571;577;587;593;599;601;607;613;617;619;631;641;643;647;653;659;661;
  673;677;683;691;701;709;719;727;733;739;743;751;757;761;769;773;787;797;809;
  811;821;823;827;829;839;853;857;859;863;877;881;883;887;907;911;919;929;937;
  941;947;953;967;971;977;983;991;997] in

  let rec indivisible k pl = match pl with 
    | [] -> true
    | h::t -> if k > h && k mod h = 0 then false else indivisible k t
  in

  let primes = L.range 2 `To mx |> L.filter (fun x -> indivisible x primes_to_1000) in

  let is_prime x = x >= 2 && indivisible x primes in

  let exps_lt x =
    let rec aux el x =
      let y = x * (L.hd el) in
      if y > mx * mx then L.rev el
      else aux (y::el) x
    in aux [x] x
  in

  let prime_exps = 
    primes |> L.flatmap (fun x -> exps_lt x) 
  in

  let rec divp k c pl = match pl with
    | [] -> (k, c)
    | h::t -> if k = 1 then (k, c)
      else if k mod h = 0 then divp (k / h) (c + 1) t
      else divp k c t
  in
  let (rem, cnt) = divp n 0 prime_exps in
  
  let rec elim_small_fc k pl = match pl with
    | [] -> k
    | h::t -> if k = 1 then k
      else if k mod h = 0 then elim_small_fc (k / h) pl
      else elim_small_fc k t
  in

  let contains_large_prime k =
    let rem = elim_small_fc k primes in
    if rem = 1 then false
    else is_prime rem
  in

  puti (if n = 1 then 0 else cnt +
    (if rem > mx && contains_large_prime rem then 1 else 0)) 
;;


Measured memory_bytes: 35396