原根(primitive root)是在數論中一個很重要的概念。

模$m$的原根(A primitive root modulo $m$)是一個正整數$g$，使得
$$g^{\varphi (m)}\equiv 1(\mathrm{mod}m)$$
且
$$g^{\gamma }\not\equiv 1(\mathrm{mod}m)$$
對$1\le \gamma <\varphi (m)$恒成立。

其中$\varphi (m)$是歐拉(Euler)函數。

對於一個模$m$的原根$g$， 他的冪$g^0,g^1,\dots ,g^{\varphi (m)-1}$組成了模$m$的簡化剩餘系(a reduced system of residues modulo $m$)。

現在你的任務就是，給你一個質數模$p$，求出$p$的最小原根。