# Identity Function

Time Limit : 5 sec, Memory Limit : 262144 KB

## 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


Source: ACM-ICPC Japan Alumni Group Summer Camp 2015 , Day 4, Tokyo, Japan, 2015-09-14
http://jag-icpc.org/
http://jag2015summer-day4.contest.atcoder.jp/