Iroha ja Kaguya ovat hiljattain ihastuneet kokonaislukuihin perustuvaan matemaattiseen peliin.

Aluksi heillä on yhteinen positiivinen kokonaisluku $n$. Pelaajat suorittavat operaatioita vuorotellen; yksi kierros määritellään siten, että sekä Iroha että Kaguya suorittavat kumpikin yhden operaation. Jokaisella kierroksella:

1. Iroha aloittaa: Hänen on valittava epänegatiivinen kokonaisluku $x$ ($0\le x<n$) ja korvattava nykyinen $n$ luvulla $n+x$.

2. Kaguya toimii toisena: Hänen on valittava alkuluku $p$, joka jakaa nykyisen luvun $n$ (eli $p\mid n$), ja korvattava nykyinen $n$ luvulla $\frac{n}{p}$.

Yllä olevia operaatioita toistetaan jatkuvasti. Jos minkä tahansa kierroksen päätyttyä $n=1$, peli päättyy välittömästi.

Pelin aikana Iroha pyrkii maksimoimaan pelattujen kierrosten kokonaismäärän, kun taas Kaguya pyrkii minimoimaan kierrosten kokonaismäärän. Olettaen, että molemmat pelaajat ovat täysin rationaalisia ja käyttävät optimaalisia strategioita, määritä kuinka monta kierrosta peli lopulta kestää.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1\le n\le10^{18}$), joka ilmaisee pelin aloitusluvun.

Tuloste

Tulosta yksi rivi, joka sisältää kokonaisluvun: kierrosten kokonaismäärän, jonka peli kestää, kun molemmat pelaajat pelaavat optimaalisesti.

Esimerkit

Syöte 1

1

Tuloste 1

0

Syöte 2

9

Tuloste 2

4

Syöte 3

16

Tuloste 3

5