Time Limit : sec, Memory Limit : KB
English

## Problem D: Identity Function

You are given an integer $N$, which is greater than 1.
Consider the following functions:

• $f(a) = a^N$ mod $N$
• $F_1(a) = f(a)$
• $F_{k+1}(a) = F_k(f(a))$ $(k = 1,2,3,...)$

Note that we use mod to represent the integer modulo operation. For a non-negative integer $x$ and a positive integer $y$, $x$ mod $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 \leq N \leq 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

3


### Output for the Sample Input

1


### Sample Input

4


### Output for the Sample Input

-1


### Sample Input

15


### Output for the Sample Input

2