MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

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

```plain
1```

* * *

### Sample Input 2

```plain
4```

### Output for the Sample Input 2

```plain
-1```

* * *

### Sample Input 3

```plain
15```

### Output for the Sample Input 3

```plain
2```

* * *