Problem description

Back
Show PDF
Dziel i zwyciężaj
(dziel-zwyciezaj)
Limit pamięci: 256 MB
Limit czasu: 1.00 s

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 
8

3

W pierwszym ruchu należy podzielić 8 przez 4, a w dwóch następnych odejmować jeden (atakować).
Wejście Wyjście Wyjaśnienie 
9

4

Wystarczy podzielić 9 przez 3, a następnie trzykrotnie eliminować po jednym żołnierzu.