给定一个大于 1 的整数 $N$。 考虑以下函数：
- $f(a) = a^N \pmod N$
- $F_1(a) = f(a)$
- $F_{k+1}(a) = F_k(f(a)) \quad (k = 1, 2, 3, \dots)$
注意，我们使用 $\text{mod}$ 表示整数取模运算。对于非负整数 $x$ 和正整数 $y$，$x \pmod y$ 是 $x$ 除以 $y$ 的余数。
输出满足对于所有小于 $N$ 的正整数 $a$，都有 $F_k(a) = a$ 的最小正整数 $k$。如果不存在这样的 $k$，则输出 $-1$。
输入格式
输入包含一行，为一个整数 $N$ ($2 \le N \le 10^9$)，其含义如题目描述中所述。
输出格式
输出满足对于所有小于 $N$ 的正整数 $a$，都有 $F_k(a) = a$ 的最小正整数 $k$；如果不存在这样的 $k$，则输出 $-1$。
样例
样例输入 1
3
样例输出 1
1
样例输入 2
4
样例输出 2
-1
样例输入 3
15
样例输出 3
2