Iroha og Kaguya hafa nýlega heillast af stærðfræðileik sem byggist á heiltölum.

Í upphafi deila þær jákvæðri heiltölu $n$. Leikmennirnir tveir skiptast á að framkvæma aðgerðir; ein umferð er skilgreind þannig að bæði Iroha og Kaguya ljúki hvor um sig einni aðgerð. Í hverri umferð:

1. Iroha gerir fyrst: Hún verður að velja óneikvæða heiltölu $x$ ($0\le x<n$) og breyta núverandi $n$ í $n+x$.

2. Kaguya gerir næst: Hún verður að velja frumtölu $p$ sem gengur upp í núverandi $n$ (þ.e. $p\mid n$) og breyta núverandi $n$ í $\frac{n}{p}$.

Aðgerðirnar hér að ofan endurtaka sig stöðugt. Ef $n=1$ í lok einhverrar umferðar lýkur leiknum samstundis.

Í leiknum stefnir Iroha að því að hámarka heildarfjölda umferða sem eru spilaðar, en Kaguya stefnir að því að lágmarka heildarfjölda umferða. Ef gert er ráð fyrir að báðir leikmenn séu fullkomlega rökvísir og beiti bestu mögulegu áætlun, vinsamlegast ákvarðaðu heildarfjölda umferða sem leikurinn mun að lokum standa yfir.

Inntak

Fyrsta línan inniheldur heiltölu $n$ ($1\le n\le10^{18}$), sem táknar upphafstölu leiksins.

Úttak

Prentaðu eina línu sem inniheldur heiltölu, sem táknar heildarfjölda umferða sem leikurinn mun standa yfir þegar báðir leikmenn spila á besta hátt.

Dæmi

Inntak 1

1

Úttak 1

0

Inntak 2

9

Úttak 2

4

Inntak 3

16

Úttak 3

5