Iroha og Kaguya har nylig blitt fascinert av et matematisk spill basert på heltall.

Til å begynne med deler de et positivt heltall $n$. De to spillerne bytter på å utføre operasjoner; én enkelt runde er definert som at både Iroha og Kaguya fullfører én operasjon hver. I hver runde:

1. Iroha går først: Hun må velge et ikke-negativt heltall $x$ ($0\le x<n$) og erstatte det nåværende $n$ med $n+x$.

2. Kaguya går som nummer to: Hun må velge et primtall $p$ som deler det nåværende $n$ (dvs. $p\mid n$) og erstatte det nåværende $n$ med $\frac{n}{p}$.

Operasjonene ovenfor gjentas kontinuerlig. Hvis $n=1$ etter slutten av en runde, avsluttes spillet umiddelbart.

I løpet av spillet ønsker Iroha å maksimere det totale antallet runder som spilles, mens Kaguya ønsker å minimere det totale antallet runder. Forutsatt at begge spillerne er fullstendig rasjonelle og bruker optimale strategier, finn det totale antallet runder spillet til slutt vil vare.

Inndata

Den første linjen inneholder et heltall $n$ ($1\le n\le10^{18}$), som representerer starttallet i spillet.

Utdata

Skriv ut én enkelt linje som inneholder et heltall, som representerer det totale antallet runder spillet vil vare gitt at begge spillerne spiller optimalt.

Eksempler

Inndata 1

1

Utdata 1

0

Inndata 2

9

Utdata 2

4

Inndata 3

16

Utdata 3

5