#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; typedef unsigned long long ull; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } ll a,b,p; inline ll mul(ll a,ll b){return (__int128)a*b%p;} inline ll qp(ll a,ll b){ ll res=1; while(b){ if(b&1)res=mul(res,a); a=mul(a,a);b>>=1; }return res; } inline ll inc(ll x){return x>=p?x-p:x;} inline ll dec(ll x){return x<0? x+p:x;} inline ll inv(ll a){return qp((a%p+p)%p,p-2);} mt19937 rnd(time(0)^clock()); namespace math{ struct pr{ll x,y;}; pr prmul(ll II,pr a,pr b){return pr{inc(mul(a.x,b.x)+mul(II,mul(a.y,b.y))),inc(mul(a.x,b.y)+mul(a.y,b.x))};} ll sqrt(ll A){ ll x=rnd()%p,y=dec(mul(x,x)-A); while(qp(y,(p-1)/2)!=p-1)x=rnd()%p,y=dec(mul(x,x)-A); pr a=pr{x,1},res=pr{1,0}; ll b=(p+1)/2; while(b){ if(b&1)res=prmul(y,res,a); a=prmul(y,a,a),b>>=1; } return res.x; } } namespace task{ ll A,B; void init(ll _a,ll _b){A=_a,B=_b;} struct nd{ ll x,y; nd(){x=-1,y=-1;} nd(ll _x,ll _y){x=_x,y=_y;} }O; bool operator<(nd a,nd b){ if(a.x!=b.x)return a.x<b.x; return a.y<b.y; } bool operator==(nd a,nd b){return a.x==b.x&&a.y==b.y;} nd operator+(nd a,nd b){ if(a==O)return b; if(b==O)return a; if(a.x==b.x&&(a.y+b.y)%p==0)return O; ll k=a.x==b.x?mul(inc(3*mul(a.x,a.x)+A),inv(2*a.y)):mul(dec(b.y-a.y),inv(b.x-a.x)); ll _b=dec(a.y-mul(a.x,k)); ll x=dec(dec(mul(k,k)-a.x)-b.x); ll y=inc(mul(k,x)+_b); return nd(x,y); } nd qp(nd a,ll b){ nd res=O; while(b){ if(b&1)res=res+a; a=a+a,b>>=1; }return res; } ll bsgs(){ ll x=rnd()%p,y=0; while(1){ ll v=inc(inc(mul(mul(x,x),x)+mul(A,x))+B); if(::qp(v,(p-1)/2)==1){ y=math::sqrt(v);break; }x=rnd()%p; } nd _={x,y}; ll sq=sqrtl(p),L=p+1-2*sq,R=p+1+2*sq; ll id=-1,c=0;nd __=qp(_,L); up(i,L,R){if(__==O)id=i,c++;__=__+_;} if(c!=1)return -1; return id; } } ll work(ll a,ll b){ task::init(a,b); return task::bsgs(); } void slv(){ a=read(),b=read(),p=read(); if(p<=500){ int res=0; up(i,0,p-1){ int z=(i*i*i+a*i+b)%p; if(!z)res++; else if(qp(z,(p-1)/2)==1)res+=1+(p!=2); } printf("%d\n",res); return; } ll delta=inc(mul(mul(a,a),mul(a,4))+mul(mul(b,b),27)); if(!delta){ if(!a)printf("%lld\n",p); else{ ll t=mul(inv((p-inc(a+a))%p),inc(inc(b+b)+b)); //a=-3t^2,b=2t^3 -> x^3-3t^2x+2t^3=0 -> (x-t)^2(x+2t)=y^2 if(qp(mul(3,t),(p-1)/2)==1)printf("%lld\n",p-1); else printf("%lld\n",p+1); } } else{ ll g=rnd()%(p-1)+1; while(qp(g,(p-1)/2)!=p-1)g=rnd()%(p-1)+1; ll c=mul(mul(a,g),g),d=mul(mul(b,g),mul(g,g)); while(1){ ll res=work(a,b); if(~res)return printf("%lld\n",res),void(); res=work(c,d); if(~res)return printf("%lld\n",2*p-res),void(); } } } int main(){ //freopen("who.in","r",stdin),freopen("who.out","w",stdout); int t=read();while(t--)slv(); return 0; }