Iroha i Kaguya ostatnio zafascynowały się matematyczną grą opartą na liczbach całkowitych.

Początkowo mają wspólną dodatnią liczbę całkowitą $n$. Obie gracze na zmianę wykonują operacje; pojedyncza runda jest zdefiniowana jako wykonanie po jednej operacji przez Irohę oraz Kaguyę. W każdej rundzie:

1. Iroha wykonuje ruch jako pierwsza: musi wybrać nieujemną liczbę całkowitą $x$ ($0\le x<n$) i zastąpić bieżące $n$ wartością $n+x$.

2. Kaguya wykonuje ruch jako druga: musi wybrać liczbę pierwszą $p$, która dzieli bieżące $n$ (tzn. $p\mid n$), i zastąpić bieżące $n$ wartością $\frac{n}{p}$.

Powyższe operacje powtarzają się nieustannie. Jeśli po zakończeniu którejkolwiek rundy zachodzi $n=1$, gra natychmiast się kończy.

Podczas gry Iroha dąży do zmaksymalizowania łącznej liczby rozegranych rund, natomiast Kaguya dąży do zminimalizowania łącznej liczby rund. Zakładając, że obie gracze są w pełni racjonalne i stosują optymalne strategie, wyznacz łączną liczbę rund, przez jaką ostatecznie potrwa gra.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1\le n\le10^{18}$), oznaczającą początkową liczbę w grze.

Wyjście

Wypisz jeden wiersz zawierający liczbę całkowitą, oznaczającą łączną liczbę rund, przez jaką potrwa gra przy optymalnej grze obu stron.

Przykłady

Wejście 1

1

Wyjście 1

0

Wejście 2

9

Wyjście 2

4

Wejście 3

16

Wyjście 3

5