#include <bits/stdc++.h>
#define ll long long
#define N 1145141919810
using namespace std;

ll T,a,b,p,m,t,tx,ans,x;

multimap<ll,ll> ma;
multimap<ll,ll>::iterator iter;

ll f(ll x,ll q){
	ll ans=1;
	
	while(q){
		if(q&1) ans*=x;
		ans%=p;
		q>>=1;
		x*=x;
		x%=p;
	}
	
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin>>T;
	while(T--){
		cin>>p>>a>>b;
		m=sqrt(p);
		if(m*m!=p) m++;
		ans=N;
		for(ll i=0;i<=m;i++){
			t=(f(a,i)*b)%p;
			ma.insert(pair<ll,ll>(t,(ll)i));
		}
		
		for(ll i=0;i<=m;i++){
			t=f(a,i*m)%p;
			if(ma.count(t)){
				auto beginItr = ma.lower_bound(t);
				auto endItr = ma.upper_bound(t);
				for (auto iter = beginItr; iter != endItr; ++iter){
					x=i*m-iter->second;
					if(x<0) continue;
					ans=min(ans,x);
				}
			}
		}
		ma.clear();
		if(ans==N){
			cout<<"no solution"<<endl;
			continue;
		}
		cout<<ans<<endl;
	}
	
	
	return 0;
}