// #pragma GCC optimize(1)
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastin ios::sync_with_stdio(false);cin.tie(0);
ll p,b,n,m,t;
map<ll,ll> dic;
// 傻逼东西调了两个小时 
inline ll qsm(ll a,ll k){
	ll res = 1;
	while(k){
		if(k&1)res=res*a%p;
        a=a*a%p;
        k>>=1;
	}
	return res;
}
void wdnmd_sb_noip_ni_ge_chu_sheng(){
   	m = ceil(sqrt(p));
   	dic[n%p] = 0;
   	for(int i=1;i<=m;i++) dic[qsm(b,i)*n%p] = i;
 	ll t=qsm(b,m),ans = 1;
  	for(int i=1;i<=m;i++){
        ans=(ans*t)%p;
        if (dic.count(ans)) {
    		cout<<i*m-dic[ans]<<endl;
   	        return ;
        }
   	}
    cout<<"no solution"<<endl;
}
int main() {
	fastin;
	cin>>t;
	while(t--){
		dic.clear();
		cin>>p>>b>>n;
    	wdnmd_sb_noip_ni_ge_chu_sheng();
	}
    return 0;
}