Time Limit: 5 sec / Memory Limit: 256 MB
Problem Statement
You are given an integer $N$, which is greater than $1$.
Consider the following functions:
- $f(a) = a^N \bmod N$
- $F_1(a) = f(a)$
- $F_{k+1}(a) = F_k(f(a))~~(k = 1,2,3,\ldots)$
Note that we use $\mathrm{mod}$ to represent the integer modulo operation. For a non-negative integer $x$ and a positive integer $y$, $x \bmod 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 \le N \le 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 1
3
Output for the Sample Input 1
1
Sample Input 2
4
Output for the Sample Input 2
-1
Sample Input 3
15
Output for the Sample Input 3
2