Problem B
Pollard's p-1 Algorithm

Notið $p-1$ reiknirit Pollard til að finna þátt, annan en töluna sjálfa eða einn, fyrir heiltölu $n$. Nota skal slembi töluna $a=2$ og jaðarinn $B$. Fyrir jaðar $B$, er átt við að talan $a^{B!}$ þarf að vera prófuð áður en við getum sagt að engin lausn hafi fundist.

Input

Fyrsta línan inniheldur heiltölu $2\le n\le 2^{63}-1$. Seinni línan inniheldur heiltölu $1\le B\le {10}^5$.

Output

Skrifið eina línu með tölu sem gengur upp í $n$ aðra en $1$ og $n$ eða $-1$ ef enginn slíkur þáttur finnst.

144948923
10

7

675103487
50000

-1