基准时间限制：1 秒 空间限制：131072 KB 分值: 0 

设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数）

 

给出1个质数P，找出P最小的原根。

Input

输入1个质数P(3 <= P <= 10^9)

Output

输出P最小的原根。

Input示例

3

Output示例

2 欧拉函数+快速幂

#include 
       
        typedef long long LL;LL m,cnt[112441],k;bool qm(LL a,LL b,LL Mod){    LL r=1%b,base=a;    while(b)    {        if(b&1)        r=r*base%Mod;        b>>=1;        base=base*base%Mod;    }    return r==1;}int main(){    scanf("%d",&m);    LL tmp=m-1;    for(LL i=2;i*i<=tmp;i++)    {        if(tmp%i==0)        {            while(tmp%i==0)                         tmp=tmp/i;            cnt[k++]=i;        }    }    if(tmp>1)         cnt[k++]=tmp;    for(LL i=2;i