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, 10¹⁸] 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.

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

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