import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; class Main { public static void main(String[] args) throws Exception { new Main().run(); } void run() { Scanner sc = new Scanner(System.in); PrintWriter pw = new PrintWriter(System.out); int T=sc.nextInt(); for(int i=0;i0) { long b=peth_root(a, div,sz, p); a=b; } } if(g>1)a=peth_root(a,g,1,p); return a; } long peth_root(long a,long p, long e, long mod) { long q=mod-1; int s=0; while(q%p==0){q/=p;++s;} long pe=pow(p,e,mod); long ans=pow(a,((pe-1)*inv(q,pe)%pe*q+1)/pe,mod); long c=2; while(pow(c,(mod-1)/p,mod)==1)++c; c=pow(c,q,mod); while(true){ long err=pow(ans,pe,mod)*inv(a,mod)%mod; int bit=s-cnt(err,p,mod);//(hoge)p^bit if(bit==s)break; ans=ans*pow(c,pow(p,bit-e,mod),mod)%mod; } return ans; } int cnt(long a,long base,long p){ int ret=0; while(a!=1){ a=pow(a,base,p); ++ret; } return ret; } long inv(long a,long p){ a%=p; long u=1,v=0; long b=p; while(b>0) { long q=a/b; a%=b; u-=v*q%p; u%=p; { u^=v;v^=u;u^=v; a^=b;b^=a;a^=b; } } return u<0?u+p:u; } long pow(long a,long n,long p){ n%=p-1; long r=1; for(;n>0;n>>=1,a=a*a%p)if(n%2==1)r=r*a%p; return r; } long gcd(long a,long b) { return a==0?b:gcd(b%a,a); } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }