#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
ll qmul(ll a,ll b,ll p){
	ll ans=1;
	for(;b;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;
	return ans;
}
ll baby_giant_step(ll a,ll b,ll p){
	ll m=sqrt(p+0.5);
	map<int,int>mp;
	for(int i=0;i<m;i++)
	mp[b]=i,b=b*a%p;
	ll x;
	for(int i=1;i<=m+1;i++){
		x=qmul(a,i*m,p);
		if(mp.count(x))return i*m-mp[x];
	}
	return -1;
}
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
ll exgcd(ll a,ll b,ll &d,ll &x,ll &y){
	if(b)exgcd(b,a%b,d,y,x),y-=x*(a/b);
	else d=a,x=1,y=0;
}
ll inv(ll a,ll p){
	ll d,x,y;
	exgcd(a,p,d,x,y);
	return d==1?(x+p)%p:-1;
}
ll log_mod(ll a,ll b,ll p){
	ll g=gcd(a,p);
	a%=p;b%=p;
	if(g==1)return baby_giant_step(a,b,p);
	else if(b%g)return -1;
	else{
		ll ans=log_mod(a,b/g*inv(a/g,p/g),p/g);
		if(ans<0)return -1;
		return ans+1;
	}
}
int main(){
	freopen("mitotic_division.in","r",stdin);
	freopen("mitotic_division.out","w",stdout);
	int T;scanf("%d",&T);
	ll a,b,c;
	while(T--){
		scanf("%lld%lld%lld",&a,&b,&c);
		ll ans=log_mod(a,b,c);
		if(ans<0)puts("no solution");
		else printf("%lld\n",ans);
	}
	return 0;
}