#include<bits/stdc++.h>
using namespace std;
int t,p,a,b;
int power(int a,int b,int p){
	int ans = 1 % p;
	for(;b;b >>= 1){
		if(b & 1) ans = (long long)ans * a % p;
		a = (long long)a * a % p;
	}
	return ans;
}
int work(int p,int a,int b){
	map<int,int> hash;
	hash.clear();
	b %= p;
	int k = (int)sqrt(p) + 1;
	for(int j = 0;j < k;j++){
		int val = (long long)b * power(a,j,p) % p;
		hash[val] = j;
	}
	a = power(a,k,p);
	if(a == 0)
		return b == 0 ? 1 : -1;
	for(int i = 0;i <= k;i++){
		int val = power(a,i,p);
		int j = hash.find(val) == hash.end() ? -1 : hash[val];
		if(j >= 0 && i * k - j >= 0)
			return i * k - j;
	}
	return -1;
}
int main(){
	cin >> t;
	while(t--){
		cin >> p >> a >> b;
		int ans = work(p,a,b);
		if(1 == b % p){
			cout << 0 << endl;
		}
		else{
			if(ans == -1){
			cout << "no solution" << endl;
		}
		else cout << ans << endl;
		}
	}
}