Problem F
Frumstæðar rætur

Frumstæðar rætur fyrir $m$ eru gildi $g$ þannig að $g^{\varphi (m)}=1(\mathrm{mod}m)$ en $g^k\ne 1(\mathrm{mod}m)$ fyrir öll $k<\varphi (m)$.

Slíkar tölur eru aðeins til ef $m=1,2,4,p^k$ eða $2p^k$ fyrir odda frumtölu $p$ og heiltölu $k\ge 1$.

Finnið slíka tölu $g$ fyrir inntakið $m$ eða segið að engin slík tala sé til.

Inntak

Fyrsta og eina lína inntaksins inniheldur jákvæða heiltölu $m>1$. Gefið er að $m\le {10}^{18}$.

Úttak

Prentið tölu $g$ eins og lýst er að ofan, sem uppfyllir $0\le g<m$. Ef engin slík tala er til prentið $-1$ í staðinn.

5

2

13

2

202

3

91

-1