在模算数中，整数 $g$ 被称为模 $n$ 意义下的原根，当且仅当所有与 $n$ 互素的数都在模 $n$ 的意义下对应了 $g$ 的幂。即，$g$ 是模 $n$ 意义下的原根，当且仅当对所有满足与 $n$ 互素的整数 $a$，都存在一个非负整数 $k$，使得 $a \equiv g^k \pmod n$。
给定一个整数 $n$，你需要找到任意一个模 $n$ 意义下的原根 ，或说明它不存在。
Input
输入的第一行包含一个整数 $n$ ($1 \le n \le 10^{16}$)。
Output
如果不存在模 $n$ 意义下的原根，输出 -1。
否则，输出一个整数 $g$，表示你找到的解。如果存在多种可能的解，你可以输出任意一个。
Example
Input 1
2Output 1
1Input 2
17Output 2
3Input 3
20014Output 3
5Input 4
230000Output 4
-1Scoring
设 $p \ge 3$ 为任意奇素数，$k > 0$ 为任意正整数。
| 测试包 | $m$ | 额外限制 |
|---|---|---|
| $1$ | $\le 1\,000$ | $m = p$ |
| $2$ | $m = p^k$ | |
| $3$ | 无 | |
| $4$ | $\le 10^6$ | $m = p$ |
| $5$ | $m = p^k$ | |
| $6$ | 无 | |
| $7$ | $\le 10^9$ | $m = p$ |
| $8$ | $m = p^k$ | |
| $9$ | 无 | |
| $10$ | $\le 10^{16}$ |