#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
unordered_map<int,int> tot;
#define int long long
int a, b, p;
int qp(int a,int b,int p)
{
	int res = 1;
	while (b > 0)
      {
		if (b & 1) 
                  res = (res * a) % p;
		b = b >> 1;
            a = (a*a) % p;
	}
	return res;
}
int q;
int32_t main()
{
      ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
      cin >> q;
      while (q -- )
      {
            bool flag = false;
            cin >> p >> a >> b;
            if (b == 1)
            {
                  cout << "0\n";
                  continue;
            }
            int m = ceil(sqrt(1.0*p)*1.0);
            int idx = b;
            for (int i = 0; i < m; i ++ )
            {
                  tot[idx] = i;
                  idx = (idx * a) % p;
            } 
            int tmp = qp(a,m,p), t = 1;
            for (int i = 0; i <= m; i ++ )
            {
                  if (tot.find(t) != tot.end())
                        if (i*m >= tot[t]) 
                        {
                              cout << i * m - tot[t] << '\n';
                              flag = true;
                              break;
                        }
                  t = (t * tmp) % p;
            }
            if (!flag)
                  cout << "no solution" << '\n';
            tot.clear();
      }
      return 0;
}