#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL __LL64
#define N 1000000
using namespace std;
typedef long long LL;
struct Node{
	LL idx;
	LL val;
}baby[N];
bool cmp(Node n1,Node n2){
	return n1.val!=n2.val?n1.val<n2.val:n1.idx<n2.idx;
}
LL gcd(LL a,LL b){
	return b==0?a:gcd(b,a%b);
}
LL extend_gcd(LL a,LL b,LL &x,LL &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	LL gcd=extend_gcd(b,a%b,x,y);
	LL t=x;
	x=y;
	y=t-a/b*y;
	return gcd;
}
LL inval(LL a,LL b,LL n){
	LL e,x,y;
	extend_gcd(a,n,x,y);
	e=((LL)x*b)%n;
	return e<0?e+n:e;
}
LL PowMod(LL a,LL b,LL MOD){
	LL ret=1%MOD,t=a%MOD;
	while(b){
		if(b&1)
			ret=((LL)ret*t)%MOD;
		t=((LL)t*t)%MOD;
		b>>=1;
	}
	return (LL)ret;
}
LL BinSearch(LL num,LL m){
	LL low=0,high=m-1,mid;
	while(low<=high){
		mid=(low+high)>>1;
		if(baby[mid].val==num)
			return baby[mid].idx;
		if(baby[mid].val<num)
			low=mid+1;
		else
			high=mid-1;
	}
	return -1;
}
LL BabyStep(LL A,LL B,LL C){
	LL tmp,D=1%C;
	LL temp;
	for(LL i=0,tmp=1%C;i<100;i++,tmp=((LL)tmp*A)%C)
		if(tmp==B)
			return i;
	LL d=0;
	while((temp=gcd(A,C))!=1){
		if(B%temp) return -1;
		d++;
		C/=temp;
		B/=temp;
		D=((A/temp)*D)%C;
	}
	LL m=(LL)ceil(sqrt((double)C));
	for(LL i=0,tmp=1%C;i<=m;i++,tmp=((LL)tmp*A)%C){
		baby[i].idx=i;
		baby[i].val=tmp;
	}
	sort(baby,baby+m+1,cmp);
	LL cnt=1;
	for(LL i=1;i<=m;i++)
		if(baby[i].val!=baby[cnt-1].val)
			baby[cnt++]=baby[i];
	LL am=PowMod(A,m,C);
	for(LL i=0;i<=m;i++,D=((LL)(D*am))%C){
		LL tmp=inval(D,B,C);
		if(tmp>=0){
			LL pos=BinSearch(tmp,cnt);
			if(pos!=-1)
				return i*m+pos+d;
		}
	}
	return -1;
}
int main(){
	freopen("mitotic_division.in","r",stdin);
	freopen("mitotic_division.out","w",stdout);
	LL T,A,B,C;
	cin>>T;
	while(T--){
		scanf("%lld%lld%lld",&A,&B,&C);
//		cout<<A<<" "<<B<<" "<<C<<endl;
		{
			LL ans,sum=1;
			for (ans=1;ans<=1000000;++ans)
			{
				sum=(sum*A) % C;
//				cout<<ans<<" "<<sum<<" "<<B<<endl;
				if (sum==B)
				{
					printf("%lld\n",ans);
					break;
				}
			}
			if (ans<=1000000) 
				continue;
		}
		if (B==1)
		{
			if (gcd(A,C)!=1)
			{
				printf("no solution\n");
				continue;
			}
			LL ans=C;
			for (LL i=2;i*i<=C;++i)
			{
				if (C%i)
				{
					for (;C%i==0;C/=i) ;
					ans=ans*(i-1)/i;
				}
			}
			printf("%d\n",ans);
		} else
		{
			LL ans=BabyStep(A,B,C);
			if(ans==-1)
				puts("no solution\n");
			else
				printf("%d\n",ans);
		}
	}
	return 0;
}