Problem F
Frumstæðar rætur

Frumstæðar rætur fyrir $m$ eru gildi $g$ þannig að $g^{\phi (m)} = 1 \pmod{m}$ en $g^k \neq 1 \pmod{m}$ fyrir öll $k < \phi (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 \geq 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$.

Úttak

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

5

2

13

2

202

3

91

-1