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
2
Output 1
1
Input 2
17
Output 2
3
Input 3
20014
Output 3
5
Input 4
230000
Output 4
-1
Scoring
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}$ |