Identity Function

Time limit5sMemory limit512 MB

Summary

Given N, find the smallest positive k with every iterate F_k(a)=a for 1<=a<N under f(a)=a^N mod N, or output -1.

Level: Hard8 of 10
Topics: Math, Number theory, Recursion
Solved: No attempts yet

Problem

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

Here $\mathrm{mod}$ denotes 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.

Examples3

Example 1
Input
```
3
```
Expected output
```
1
```
Example 2
Input
```
4
```
Expected output
```
-1
```
Example 3
Input
```
15
```
Expected output
```
2
```