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.

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

3

1

4

-1

15

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/

http://jag-icpc.org/

http://jag2015summer-day4.contest.atcoder.jp/