Iterated Euler Totient Function

Elliot discovered a number N on her quilt. She believes that by finding the smallest non-negative integer x such that \(\varphi^{x}(N)=1\), she will obtain a clue about the aliens who once kidnapped her. Here, \(\varphi(n)\) denotes Euler's Totient Function. Your task is to help her by calculating the minimum x for a given N.

Note: \(\varphi^{0}(N)\) is defined as N itself. For instance, if N=1, then \(\varphi^{0}(1)=1\) and the answer is 0.

inputFormat

The input consists of a single integer N (1 ≤ N). The integer is given in one line.

outputFormat

Output the minimum number of iterations x such that \(\varphi^{x}(N)=1\).

sample

1

0