ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Tavrida NU Akai contest. Petrozavodsk training camp. Summer 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Troubles with Pollard

Time limit: 0.5 second
Memory limit: 64 MB
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:
  1. If n is prime, return n.
  2. Otherwise, choose a random r in the range [1, 1018] and calculate g, the greatest common divisor of n and r.
  3. 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.

Input

The only input line contains an integer n (2 ≤ n ≤ 109).

Output

Output the expected number of times the greatest common divisor will be calculated, with absolute or relative error not exceeding 10−6.

Samples

inputoutput
12
4.8571428571
8
6.6666666667
Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010
To submit the solution for this problem go to the Problem set: 1816. Troubles with Pollard