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 ≤ 10⁹

Przykład

8

3

9

4