#include <cstdio>
#include <map>
#include <cmath>
#include <vector>
#include <cassert>
using namespace std;

int M[2000100];
long long P;

long long exp(long long a,long long e) {
    long long ans=0;
    long long bas=a;
    for(int b=0;(1<<b)<=e;b++) {
        if(e&(1<<b)) {
            ans=(ans+bas)%P;
        }
        bas=((long long)bas*bas)%P;
    }
    return ans;
}


int solve(long long a,long long start) {
    if(start==1) {
        return 0;
    }
    vector<int> A;
    
    int sp=sqrt(P);
    long long val=exp(a,sp);
    long long x=val;
    for(int i=1;i<=sp;i++) {
        M[val]=i*sp;
        A.push_back(val);
        val=(val*x)%P;
    }
    M[1]=P-1;
    A.push_back(1);

    int pas=0;
    while(M[start]==0) {
        start=((long long)start*a)%P;
        pas++;
    }
    int ans=M[start]-pas;

    for(vector<int>::iterator it=A.begin(); it!=A.end(); it++) {
        M[*it]=0;
    }

    return ans;
}

int main() {
    freopen("dlog.in","r",stdin);
    freopen("dlog.out","w",stdout);
    
    int t;
    for(scanf("%d",&t);t;t--) {
        long long G,Y;
        scanf("%lld%lld%lld",&P,&G,&Y);
        printf("%d\n",solve(G,Y));
    }
    

    return 0;
}