#include<bits/stdc++.h> #define int long long using namespace std; int n,q,s; inline int qpow(int a,int b,int mod){ int Ans=1; while(b){ if(b&1)Ans=Ans*a%mod; a=a*a%mod;b>>=1; }return Ans; } inline void slv(){ cin>>n>>s>>q; int Ans=0; for(int i=0;i<n;i++)if((qpow(i,q,n)+i*q)%n==s)(Ans+=i%q)%=q; cout<<Ans<<endl; } signed main(){ #ifndef ONLINE_JUDGE freopen("ticket.in","r",stdin); freopen("ticket.out","w",stdout); #endif int T;cin>>T; while(T--)slv(); return 0; }