Once Alexander decided to learn Pollard's method. However,
he didn't understand this method well enough, and as a result he
implemented the following algorithm which decomposes an integer n:
- If n is prime, return n.
- Otherwise, choose a random r
in the range [1, 1018] and calculate g, the greatest common divisor
of n and r.
- If g = 1 or g = n, repeat step 2, otherwise
run the algorithm recursively for numbers g and n/g and
return the union of the resulting divisor lists.
Alexander wants to know the number of times the greatest common divisor will
be calculated at step 2 for a given n. Help him find this number.
The only input line contains an integer n (2 ≤ n ≤ 109).
Output the expected number of times the greatest common divisor
will be calculated, with absolute or relative error not exceeding 10−6.
Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010