问题陈述
给你一个整数 $N$,它大于 $1$。
考虑以下功能:
- $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$,使得 $F_k(a) = a$ 对于所有小于 $N$ 的正整数 $a$。 如果不存在这样的$k$,则输出$-1$。
输入
输入由一行组成,其中包含一个整数 $N$ ($2 \le N \le 10^9$),其含义在问题陈述中描述。
输出
输出最小正整数 $k$,使得对于所有小于 $N$ 的正整数 $a$,$F_k(a) = a$;如果不存在这样的 $k$,则输出 $-1$。
示例输入 1
3
样本输入 1 的输出
1
示例输入 2
4
样本输入 2 的输出
-1
示例输入 3
15
样本输入 3 的输出
2