In modular arithmetic, a number $g$ is a primitive root modulo $n$ if every number a coprime to $n$ is congruent to a power of $g$ modulo $n$. That is, $g$ is a primitive root modulo $n$ if for every integer $a$ coprime to $n$, there is some integer $k$ for which $g^k \equiv a \pmod n$.
Given an integer $n$, you need to find any primitive root modulo $n$, or claim that it doesn't exist.
Input
The first line of the input consists a single integer $n$ ($1 \le n \le 10^{16}$).
Output
If there's no primitive root modulo $n$, print -1.
Otherwise, print a single integer $g$, indicating your solution. If there are multiple possible solutions, you may print any of them.
Example
Input 1
2Output 1
1Input 2
17Output 2
3Input 3
20014Output 3
5Input 4
230000Output 4
-1Scoring
Let $p \ge 3$ be an odd prime number, and $k > 0$ be a positive integer.
| Test Set | $m$ | Constraints |
|---|---|---|
| $1$ | $\le 1\,000$ | $m = p$ |
| $2$ | $m = p^k$ | |
| $3$ | None | |
| $4$ | $\le 10^6$ | $m = p$ |
| $5$ | $m = p^k$ | |
| $6$ | None | |
| $7$ | $\le 10^9$ | $m = p$ |
| $8$ | $m = p^k$ | |
| $9$ | None | |
| $10$ | $\le 10^{16}$ |