Iroha et Kaguya se sont récemment passionnées pour un jeu mathématique basé sur les nombres entiers.

Initialement, elles partagent un entier strictement positif $n$. Les deux joueuses effectuent des opérations à tour de rôle ; une manche est définie par le fait qu'Iroha et Kaguya accomplissent chacune une opération. À chaque manche :

1. Iroha joue en premier : elle doit choisir un entier naturel $x$ ($0\le x<n$) et remplacer le $n$ actuel par $n+x$.

2. Kaguya joue en second : elle doit choisir un nombre premier $p$ qui divise le $n$ actuel (c'est-à-dire $p\mid n$) et remplacer le $n$ actuel par $\frac{n}{p}$.

Les opérations ci-dessus se répètent continuellement. Si $n=1$ à la fin d'une manche quelconque, la partie se termine immédiatement.

Pendant la partie, Iroha cherche à maximiser le nombre total de manches jouées, tandis que Kaguya cherche à minimiser le nombre total de manches. En supposant que les deux joueuses sont parfaitement rationnelles et adoptent des stratégies optimales, veuillez déterminer le nombre total de manches que durera finalement la partie.

Entrée

La première ligne contient un entier $n$ ($1\le n\le10^{18}$), représentant le nombre initial du jeu.

Sortie

Affichez une seule ligne contenant un entier, représentant le nombre total de manches que durera la partie si les deux joueuses jouent de manière optimale.

Exemples

Entrée 1

1

Sortie 1

0

Entrée 2

9

Sortie 2

4

Entrée 3

16

Sortie 3

5