记录编号	240418	评测结果	AAAAAAAAAA
题目名称	多-有丝分裂	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.169 s
提交时间	2016-03-22 20:58:22	内存使用	2.24 MiB

#define M 10007
#define Msize 100000

#define ll long long

#include<cmath>
#include<cstdio>
#include<cstring>

using namespace std;

struct HashTable{
	ll val[Msize],idx[Msize];
	int first[M],next[Msize],siz;
	void clear(){memset(first,-1,sizeof(first));siz=0;}
	void insert(ll value,ll key){
		int _hash=value%M;
		for(int i=first[_hash];i!=-1;i=next[i])
		    if(val[i]==value)return;
		val[siz]=value;idx[siz]=key;
		next[siz]=first[_hash];first[_hash]=siz++;
	}
	ll find(ll value){
		int _hash=value%M;
		for(int i=first[_hash];i!=-1;i=next[i])
		    if(val[i]==value)return idx[i];
		return -1;
	}
}hash;

int Case;
ll A,B,P,x,y,res;

ll gcd(ll a,ll b){return (!b)?a:gcd(b,a%b);}

ll Quick_pow(ll p,ll q)
{
	ll ret=1;
	while(q){
		if(q&1)ret=(ret*p)%P;
		q>>=1;p=(p*p)%P;
	}return ret;
}

ll exgcd(ll a,ll b)
{
	if(!b){x=1,y=0;return a;}
	ll d=exgcd(b,a%b);
	ll p=x;x=y;y=p-(a/b)*y;
	return d;
}

ll inverse(ll a){exgcd(a,P);return (x%P+P)%P;}

ll BSGS()
{
	ll m=ceil(sqrt(P)),p=1;
	hash.insert(1,0);
	for(ll i=1;i<m;i++){
		(p*=A)%=P;
		if(p==B)return i;
		hash.insert(p,i);
	}
    (p*=A)%=P;ll ret=1,d;
    for(ll i=1,j;i<=m;i++){
        (ret*=p)%=P;
        d=exgcd(ret,P);//D^k*x=B(mod P)  re*x+P*y=B
  		(x*=B)%=P;x=(x%P+P)%P;
		j=hash.find(x);
		if(j!=-1) return i*m+j;
    }
	return -1;
}

ll EXBSGS()
{
	ll m=ceil(log2(P)),p=1;
	for(ll i=1;i<=m;i++){
		(p*=A)%=P;
		if(p==B)return i;
	}
	ll d=gcd(A,P),sum=1,ret=0;
	while(d!=1){
		ret++;
		if(B%d)return -1;
        (sum*=(A/d))%=P;
        P/=d;B/=d;
        d=gcd(A,P);
	}
	B=B*inverse(sum)%P;
	ll rest=BSGS();
	if(rest==-1)return -1;
	return rest+ret;
}

int main()
{
    freopen("mitotic_division.in","r",stdin);
	freopen("mitotic_division.out","w",stdout);
	scanf("%d",&Case);
	while(Case--){
		scanf("%lld%lld%lld",&A,&B,&P);
		hash.clear();
		res=EXBSGS();//A^x=B(mod P)
		if(res!=-1)printf("%lld\n",res);
		else puts("no solution");
	}
}