Iroha y Kaguya se han aficionado recientemente a un juego matemático basado en enteros.

Al principio, comparten un entero positivo $n$. Las dos jugadoras se turnan para realizar operaciones; una ronda se define como una operación de Iroha y una de Kaguya. En cada ronda:

1. Iroha juega primero: debe elegir un entero no negativo $x$ ($0\le x<n$) y sustituir el $n$ actual por $n+x$.

2. Kaguya juega después: debe elegir un número primo $p$ que divida el $n$ actual (es decir, $p\mid n$) y sustituir el $n$ actual por $\frac{n}{p}$.

Las operaciones anteriores se repiten continuamente. Si $n=1$ al terminar cualquier ronda, el juego acaba inmediatamente.

Durante el juego, Iroha intenta maximizar el número total de rondas, mientras que Kaguya intenta minimizarlo. Suponiendo que ambas jugadoras son perfectamente racionales y utilizan estrategias óptimas, determina el número total de rondas que durará finalmente el juego.

Entrada

La primera línea contiene un entero $n$ ($1\le n\le10^{18}$), que representa el número inicial del juego.

Salida

Imprime una sola línea con un entero que represente el número total de rondas que durará el juego si ambas jugadoras juegan de forma óptima.

Ejemplos

Entrada 1

1

Salida 1

0

Entrada 2

9

Salida 2

4

Entrada 3

16

Salida 3

5