16808번 - Identity Function 다국어

문제

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$.

입력

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 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.

제한

힌트