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://acm-icpc.aitea.net/
http://jag2015summer-day4.contest.atcoder.jp/