Ироха и Кагуя недавно увлеклись математической игрой с целыми числами.
Изначально у них есть общее положительное целое число $n$. Два игрока по очереди выполняют операции; один раунд определяется как выполнение ровно одной операции сначала Ирохой, а затем Кагуей. В каждом раунде:
Ироха ходит первой: она должна выбрать неотрицательное целое число $x$ ($0\le x<n$) и заменить текущее $n$ на $n+x$.
Кагуя ходит второй: она должна выбрать простое число $p$, которое делит текущее $n$ (то есть $p\mid n$), и заменить текущее $n$ на $\frac{n}{p}$.
Вышеуказанные операции непрерывно повторяются. Если после окончания какого-либо раунда оказывается, что $n=1$, игра немедленно заканчивается.
В ходе игры Ироха стремится максимизировать общее количество сыгранных раундов, а Кагуя стремится минимизировать общее количество раундов. Предполагая, что оба игрока абсолютно рациональны и придерживаются оптимальных стратегий, определите общее количество раундов, которое в итоге продлится игра.
Входные данные
Первая строка содержит целое число $n$ ($1\le n\le10^{18}$) — начальное число в игре.
Выходные данные
Выведите единственную строку, содержащую целое число — общее количество раундов, которое продлится игра при оптимальной игре обоих игроков.
Примеры
Входные данные 1
1
Выходные данные 1
0
Входные данные 2
9
Выходные данные 2
4
Входные данные 3
16
Выходные данные 3
5