Problem D: Identity Function

You are given an integer $N$, which is greater than 1.
Consider the following functions:

• $f(a) = a^N$ mod $N$
• $F_1(a) = f(a)$
• $F_{k+1}(a) = F_k(f(a))$ $(k = 1,2,3,...)$

Note that we use mod to represent the integer modulo operation. For a non-negative integer $x$ and a positive integer $y$, $x$ mod $y$ is the remainder of $x$ divided by $y$.

Output the minimum positive integer $k$ such that $F_k(a) = a$ for all positive integers $a$ less than $N$. If no such $k$ exists, output -1.

Input

The input consists of a single line that contains an integer $N$ ($2 \leq N \leq 10^9$), whose meaning is described in the problem statement.

Output

Output the minimum positive integer $k$ such that $F_k(a) = a$ for all positive integers $a$ less than $N$, or -1 if no such $k$ exists.

Sample Input

3

Output for the Sample Input

1

Sample Input

4

Output for the Sample Input

-1

Sample Input

15

Output for the Sample Input

2