Hide

Problem F
Frumstæðar rætur

Languages en is

Frumstæðar rætur fyrir m eru gildi g þannig að gϕ(m)=1(modm) en gk1(modm) fyrir öll k<ϕ(m).

Slíkar tölur eru aðeins til ef m=1,2,4,pk eða 2pk fyrir odda frumtölu p og heiltölu k1.

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 0g<m. Ef engin slík tala er til prentið 1 í staðinn.

Sample Input 1 Sample Output 1
5
2
Sample Input 2 Sample Output 2
13
2
Sample Input 3 Sample Output 3
202
3
Sample Input 4 Sample Output 4
91
-1
Hide