#include <iostream>
using namespace std;
int main()
{
	freopen("mitotic_division.in", "r", stdin);
	freopen("mitotic_division.out", "w", stdout);
	int n;
	cin>>n;
	for(; n > 0; n--)
	{
		long long a,b,c;
		cin>>a>>b>>c;
		long long now = a, sum = 1;
		while (now % c !=b && sum <= 1000000)
		{
			now = (now * a) % c;
			sum++;
		}
		if (sum > 1000000)
			printf("no solution\n");
		else
			printf("%d\n", sum);
	}
	return 0;
}