Іроха та Каґуя нещодавно захопилися математичною грою на основі цілих чисел.

Спочатку вони мають спільне додатне ціле число $n$. Обидва гравці по черзі виконують операції; один раунд визначається як виконання по одній операції і Ірохою, і Каґуєю. У кожному раунді:

1. Іроха ходить першою: вона повинна вибрати невід'ємне ціле число $x$ ($0\le x<n$) і замінити поточне $n$ на $n+x$.

2. Каґуя ходить другою: вона повинна вибрати просте число $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