Однажды Александр решил изучить метод Полларда. Однако он плохо разобрался в теории и в результате написал следующий алгоритм разложения числа n на простые множители:

1. Если n простое, вернуть n.
2. В противном случае, выбрать случайное r из отрезка [1, 10¹⁸] и вычислить g — наибольший общий делитель n и r.
3. Если g = 1 или g = n, повторить шаг 2, в противном случае рекурсивно вызвать алгоритм для чисел g и n/g и вернуть объединение полученных списков множителей.

Александру стало интересно, сколько раз для данного числа n в процессе работы алгоритма будет вычислен наибольший общий делитель на шаге 2. Помогите ему узнать это.

В единственной строке записано целое число n (2 ≤ n ≤ 10⁹).

Выведите единственное число — ожидаемое количество раз, которое будет вычислен наибольший общий делитель, с абсолютной или относительной погрешностью не более 10⁻⁶.