ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

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