#include <bits/stdc++.h>
 using namespace std;
 #define rep(i,a,b) for(int i=a;i<=b;++i)
 typedef long long ll;
 ;
 ll mul(ll x,ll y,ll p) {
     x%=p; y%=p;
     return (x*y-(ll)((long double)x/p*y+0.5)*p+p)%p;
 }
 ll _pow(ll x,ll n,ll p) {
     ll ret=;
     ,x=mul(x,x,p)) ) ret=mul(ret,x,p);
     return ret;
 }
 ll tp[]={2LL,3LL,5LL,7LL,13LL,61LL};
 bool MR(ll n) {
     ) return false;
     rep(i,,) if(n==tp[i]) return true;
     rep(i,,) ) return false;
     rep(i,,) {
         ll tmp=n-;)) tmp>>=;
         ll s=_pow(tp[i],tmp,n);
         &&s!=&&tmp!=n-) tmp<<=,s=mul(s,s,n);
         &&!(tmp&)) return false;
     }
     return true;
 }
 ll PR(ll n,ll c) {
     ll i=,k=2LL,x,y; x=y=1LL+rand()%(n-);
     ) {
         x=(mul(x,x,n)+c)%n;
         ll d=__gcd((y-x+n)%n,n);
         &&d!=n) return d;
         if(x==y) return n;
         ;
     }
 }
 int op[maxn],len,cnt,T;
 ll n,P,K,ans,gt[maxn];
 inline void fct(ll n) {
     ) return;
     if(MR(n)){gt[++len]=n;return;}
     ll p=n;
     ;p==n;--c) p=PR(p,c);
     fct(p); fct(n/p);
 }
 ll fpow(ll x,ll n,ll p) {
     ll ret=;
     ,x=x*x%p)
         ) ret=ret*x%p;
     return ret;
 }
 ll g(ll n) {,P);}
 ll f(ll n) {?n%P:(n>>)%P;}
 inline void dfs(int dp,ll d,ll pro) {
     ) {
         )&&(d&)==) return;
         (ans+=1LL*g(n/d)*f(n/d)%P*pro%P)%=P;
         return;
     }
     dfs(dp+,d,pro); pro=1LL*pro*(+P-gt[dp]%P)%P;
     rep(i,,op[dp]) d*=gt[dp],dfs(dp+,d,pro);
 }
 int main() {
 #ifndef ONLINE_JUDGE
     freopen("25.in","r",stdin);
 #endif
     scanf();
     while(T--) {
         scanf("%lld%lld%lld",&n,&K,&P);K%=P;
         len=cnt=;++cnt;
         memset(gt,,,sizeof(op));
         fct(n);
         sort(gt+,gt++len);
         rep(i,,len) {
             ;
             ++op[cnt];
         }
         ans=;dfs(,1LL,1LL);printf("%lld\n",ans);
     }
     ;
 }