main=map read.words<$>getLine>>=print.(\x->f(if(even x)then 2 else 1)3(g x 2)).(\(a:[b])->gcd a b)
 where f ans uo hai | hai==1    = ans
                    | uo*uo>hai = ans+1
                    | (mod hai uo)==0 = f (ans+1) (uo+2) (g hai uo)
                    |otherwise  = f ans (uo+2) hai
       g x i = if(mod x i)==0 then(g(quot x i)i)else x