Iroha och Kaguya har nyligen blivit fascinerade av ett matematiskt spel baserat på heltal.

Från början delar de på ett positivt heltal $n$. De två spelarna turas om att utföra operationer; en runda definieras som att både Iroha och Kaguya slutför varsin operation. I varje runda:

1. Iroha börjar: Hon måste välja ett icke-negativt heltal $x$ ($0\le x<n$) och ersätta det nuvarande $n$ med $n+x$.

2. Kaguya går som tvåa: Hon måste välja ett primtal $p$ som delar det nuvarande $n$ (dvs. $p\mid n$) och ersätta det nuvarande $n$ med $\frac{n}{p}$.

Ovanstående operationer upprepas kontinuerligt. Om $n=1$ efter slutet av någon runda avslutas spelet omedelbart.

Under spelets gång strävar Iroha efter att maximera det totala antalet spelade rundor, medan Kaguya strävar efter att minimera det totala antalet rundor. Under antagandet att båda spelarna är fullständigt rationella och använder optimala strategier, bestäm det totala antalet rundor som spelet slutligen kommer att pågå.

Indata

Den första raden innehåller ett heltal $n$ ($1\le n\le10^{18}$), som representerar spelets starttal.

Utdata

Skriv ut en enda rad som innehåller ett heltal, vilket representerar det totala antalet rundor spelet kommer att pågå givet att båda spelarna spelar optimalt.

Exempel

Indata 1

1

Utdata 1

0

Indata 2

9

Utdata 2

4

Indata 3

16

Utdata 3

5