#include<cstdio>
#include<climits>
using namespace std;
long long n,a,b,c,ans;
int main(){
	freopen("mitotic_division.in","r",stdin);
	freopen("mitotic_division.out","w",stdout);
	scanf("%d",&n);
	while(n--){
		ans=1;
		scanf("%d%d%d",&a,&b,&c);
		long long fac=a;
		int i;
		for(i=1;i<=100;i++) {
			if(fac%c==b) break;
			fac=(fac*(a%c))%c;
			ans++;
		}
		if(i>100) printf("no solution\n");
		else printf("%d\n",ans);
	}
}