MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], processEscapes: true }}); 

### 问题描述

给定一个大于1的整数$N$。

考虑以下函数：

- $f(a) = a^N \bmod N$
- $F_1(a) = f(a)$
- $F_{k+1}(a) = F_k(f(a))~~(k = 1,2,3,\ldots)$

注意，我们使用$\mathrm{mod}$来表示整数模运算。对于非负整数$x$和正整数$y$，$x \bmod y$是$x$除以$y$的余数。

输出最小的正整数$k$，使得对于小于$N$的所有正整数$a$都满足$F_k(a) = a$。如果不存在这样的$k$，则输出$-1$。

* * *

### 输入

输入由一行组成，包含一个整数$N$（$2 \le N \le 10^9$），它的含义如问题描述中所述。

### 输出

输出最小的正整数$k$，使得对于小于$N$的所有正整数$a$都满足$F_k(a) = a$，如果不存在这样的$k$，则输出$-1$。

* * *

### 示例输入 1

```plain
3```

### 示例输出 1

```plain
1```

* * *

### 示例输入 2

```plain
4```

### 示例输出 2

```plain
-1```

* * *

### 示例输入 3

```plain
15```

### 示例输出 3

```plain
2```

* * *