Iroha und Kaguya sind seit Kurzem von einem mathematischen Spiel fasziniert, das auf ganzen Zahlen basiert.

Zu Beginn teilen sie sich eine positive ganze Zahl $n$. Die beiden Spielerinnen führen abwechselnd Operationen aus; eine einzelne Runde ist dadurch definiert, dass sowohl Iroha als auch Kaguya jeweils eine Operation abschließen. In jeder Runde gilt:

1. Iroha zieht zuerst: Sie muss eine nichtnegative ganze Zahl $x$ ($0\le x<n$) wählen und das aktuelle $n$ durch $n+x$ ersetzen.

2. Kaguya zieht als Zweite: Sie muss eine Primzahl $p$ wählen, die das aktuelle $n$ teilt (d. h. $p\mid n$), und das aktuelle $n$ durch $\frac{n}{p}$ ersetzen.

Die obigen Operationen wiederholen sich fortlaufend. Wenn am Ende einer beliebigen Runde $n=1$ gilt, endet das Spiel sofort.

Während des Spiels versucht Iroha, die Gesamtzahl der gespielten Runden zu maximieren, während Kaguya versucht, die Gesamtzahl der Runden zu minimieren. Unter der Annahme, dass beide Spielerinnen vollkommen rational handeln und optimale Strategien verfolgen, bestimme bitte die Gesamtzahl der Runden, die das Spiel letztendlich dauern wird.

Eingabe

Die erste Zeile enthält eine ganze Zahl $n$ ($1\le n\le10^{18}$), welche die Anfangszahl des Spiels darstellt.

Ausgabe

Gib eine einzige Zeile mit einer ganzen Zahl aus, welche die Gesamtzahl der Runden darstellt, die das Spiel dauert, wenn beide Spielerinnen optimal spielen.

Beispiele

Eingabe 1

1

Ausgabe 1

0

Eingabe 2

9

Ausgabe 2

4

Eingabe 3

16

Ausgabe 3

5