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