Problem description
Jasio gra w Dziel i zwyciężaj. Zasady są bardzo proste. Na początku przeciwnik dysponuje armią N żołnierzy. W każdej turze Jasio może wykonać jedną z dwóch operacji: zaatakować zmniejszając liczebność armii przeciwnika o jeden lub podzielić liczebność armii przeciwnika przez dowolny właściwy dzielnik.
Na przykład po podzieleniu 12 przez 4 przeciwnikowi zostaje 3 żołnierzy. Poza tym można podzielić 12 przez 3 lub 2, ale nie można przez 12 (ten dzielnik nie jest właściwy). Gdy przeciwnik straci wszystkich żołnierzy, gra kończy się, a Jasio wygrywa. Jasio bardzo lubi zwyciężać, ale jeszcze niezbyt dobrze umie dzielić. Pomóż mu i napisz program, który obliczy, w jakiej najmniejszej liczbie ruchów może osiągnąć upragnione zwycięstwo.
Wejście
W jedynym wierszu wejścia znajduje się jedna liczba naturalna N, liczba żołnierzy w armii przeciwnika.
Wyjście
Wypisz jedną liczbę naturalną, minimalną liczbę ruchów potrzebną do wyeliminowania wszystkich żołnierzy przeciwnika.
Ograniczenia
1 ≤ N ≤ 109
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
W pierwszym ruchu należy podzielić 8 przez 4, a w dwóch następnych odejmować jeden (atakować). |
| Wejście | Wyjście | Wyjaśnienie |
|
|
Wystarczy podzielić 9 przez 3, a następnie trzykrotnie eliminować po jednym żołnierzu. |