Problem F
Primitive Roots

Primitive roots modulo $m$ are values $g$ such that $g^{\phi (m)} = 1 \pmod{m}$ but $g^k \neq 1 \pmod{m}$ for all $k < \phi (m)$.

Such values only exist if $m = 1, 2, 4, p^k$ or $2p^k$ where $p$ is an odd prime and $k \geq 1$.

Find such a value $g$ for $m$ or report that it does not exist.

Input

The first and only line of input contains a positive integer $m > 1$.

Output

Print a primitive root $g$ modulo $m$. It should satisfy $0 \leq g < m$. If no such root exists, print $-1$.

5

2

13

2

202

3

91

-1