#include <map>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (ll i=j;i<=k;++i)

#define D(i,j,k) for (ll i=j;i>=k;--i)

#define ll long long

map <ll,ll> mp;

ll t,k;

ll qpow(ll a,ll b,ll p)

{

    ll ret=1;

    while (b)

    {

        if (b&1) ret=(ll)ret*a%p;

        a=(ll)a*a%p;

        b>>=1;

    }

    return ret;

}

void solve1()

{

    F(i,1,t)

    {

        ll a,b,p;

        scanf("%lld%lld%lld",&a,&b,&p);

        printf("%lld\n",qpow(a,b,p));

    }

}

void exgcd(ll a,ll b,ll &d,ll &x,ll &y)

{

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

    exgcd(b,a%b,d,y,x);

    y-=x*(a/b);

}

void solve2()

{

    F(i,1,t)

    {

        ll a,b,p,x,y,z,d;

        scanf("%lld%lld%lld",&a,&b,&p);b%=p;

        exgcd(a,p,d,x,y);

        if (b%d)

        {

            printf("Orz, I cannot find x!\n");

            continue;

        }

        x=x*(b/d);

        if (x>=0) x=x%p;

        else x=(0-x)/p*p+x;

        while (x<0) x+=p;

        printf("%lld\n",x);

    }

}

void solve3()

{

    F(i,1,t)

    {

        ll a,b,c;

        scanf("%lld%lld%lld",&a,&b,&c);

        mp.clear();

        if (a%c==0) {printf("Orz, I cannot find x!\n");continue;}

        ll p=false;

        ll m=ceil(sqrt(c)),ans;

        for (ll i=0;i<=m;++i)

        {

            if (i==0)

            {

                ans=b%c;mp[ans]=i;continue;

            }

            ans=((ll)ans*a)%c;

            mp[ans]=i;

        }

        ll tmp=qpow(a,m,c); ans=1;

        for (ll i=1;i<=m;++i)

        {

            ans=((ll)ans*tmp)%c;

            if (mp[ans])

            {

                ll tmp=i*m-mp[ans];

                printf("%lld\n",(tmp%c+c)%c);

                p=true;

                break;

            }

        }

        if (!p) printf("Orz, I cannot find x!\n");

    }

}

int main()

{

    scanf("%lld%lld",&t,&k);

    switch(k)

    {

        case 1: solve1(); break;

        case 2: solve2(); break;

        case 3: solve3(); break;

    }

}