%%% Orz ,筛素数到sqrt(n),分解ϕ(p)，依次枚举判断就好了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 100000#define LL long longusing namespace std;LL prime[100010],tot,cnt,p[100010],n;bool bo[100010],flag;void init(){    for(int i=2;i<=N;i++){        if(!bo[i])prime[++tot]=i;        for(int j=1;j<=tot&&i*prime[j]<=N;j++){            bo[i*prime[j]]=1;            if(i%prime[j]==0)break;        }    }}void divide(int x){    cnt=0;    for(int i=1;prime[i]*prime[i]<=x;i++){        if(x%prime[i]==0){            p[++cnt]=prime[i];            while(x%prime[i]==0)x/=prime[i];        }    }    p[++cnt]=x;}LL qpm(LL x,LL y,LL z){    LL ans=1;    while(y){        if(y&1) ans=(ans*x)%z;        x=(x*x)%z;y>>=1;    }    return ans;}int main(){    scanf("%lld",&n);    init();    divide(n-1);    for(int i=2;i