Problem F
Primitive Roots

Primitive roots modulo $m$ are values $g$ such that $g^{\varphi (m)}=1(\mathrm{mod}m)$ but $g^k\ne 1(\mathrm{mod}m)$ for all $k<\varphi (m)$.

Such values only exist if $m=1,2,4,p^k$ or $2p^k$ where $p$ is an odd prime and $k\ge 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\le g<m$. If no such root exists, print $-1$.

5

2

13

2

202

3

91

-1