시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 4 4 3 100.000%

문제

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.

예제 입력 1

3

예제 출력 1

1

예제 입력 2

4

예제 출력 2

-1

예제 입력 3

15

예제 출력 3

2