#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back #define inx(u) int I=h[(u)],v=edge[I].v,w=edge[I].w;I;I=edge[I].nx,v=edge[I].v,w=edge[I].w int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} const int MAXN=1000010,M=60,N=20;int Mod; void add(int &x,int y){x+=y;if(x>=Mod)x-=Mod;}int Pow(int x,int y,int M){int rt=1;while(y){if(y&1)rt=rt*x%M;x=x*x%M,y>>=1;}return rt;} int n,s,q,a[MAXN],ans; int p[M],cnt,dy[MAXN]; void slv(){ n=read(),s=read(),q=Mod=read(); ans=0; for(int i=1;i<n;i++){ int tmp=(Pow(i,q,n)+i*q)%n; if(tmp==s)add(ans,i); } printf("%lld\n",ans%Mod); } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); int _=read();while(_--) slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }