#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin ("dlog.in");
ofstream fout ("dlog.out");

int euclid_extins (int a,int b,int &x,int &y) 
{
    int d,x0,y0;

    if (b==0) 
	{
        x=1; 
		y=0;
        return a;
    }

    d=euclid_extins (b,a%b,x0,y0);
    x=y0; 
	y=x0-(a/b)*y0;

    return d;
}

void solve () 
{
    int i,contor,inv,p,g,y;
	int root=0, rootinv=0;
    fin>>p>>g>>y;

    euclid_extins (g,p,inv,contor);
  
	if (inv<0)
        inv=p+inv%p;
    root=1; 
	rootinv=1;

    for (i=0; i<p; ++i) 
	{
        if (root==y) 
		{
			fout<<i<<'\n';
            return ;
        }
        root=(1LL*root*g)%p;

        /*if (rootinv==y) 
		{
			fout<<p-i-1<<'\n';
            return ;
        }
        rootinv=(1LL*rootinv*inv)%p;*/
    }
}

int main () 
{
	int t;
    fin>>t;
    for (;t;--t)
        solve ();
	return 0;
}