Iroha e Kaguya sono rimaste recentemente affascinate da un gioco matematico basato sui numeri interi.
Inizialmente condividono un intero positivo $n$. Le due giocatrici eseguono operazioni a turno; un singolo round è definito dal completamento di un'operazione ciascuna da parte sia di Iroha che di Kaguya. In ogni round:
Iroha muove per prima: deve scegliere un intero non negativo $x$ ($0\le x<n$) e sostituire l'$n$ corrente con $n+x$.
Kaguya muove per seconda: deve scegliere un numero primo $p$ che divide l'$n$ corrente (cioè $p\mid n$) e sostituire l'$n$ corrente con $\frac{n}{p}$.
Le operazioni precedenti si ripetono continuamente. Se $n=1$ al termine di un round qualsiasi, il gioco termina immediatamente.
Durante il gioco, Iroha mira a massimizzare il numero totale di round giocati, mentre Kaguya mira a minimizzare il numero totale di round. Supponendo che entrambe le giocatrici siano perfettamente razionali e adottino strategie ottimali, determina il numero totale di round che il gioco durerà complessivamente.
Input
La prima riga contiene un intero $n$ ($1\le n\le10^{18}$), che rappresenta il numero iniziale del gioco.
Output
Stampa una singola riga contenente un intero, che rappresenta il numero totale di round che il gioco durerà assumendo che entrambe le giocatrici giochino in modo ottimale.
Esempi
Input 1
1
Output 1
0
Input 2
9
Output 2
4
Input 3
16
Output 3
5