#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#include<cmath>

#define ll long long

using namespace std;

ll T,type,A,B,C,x,y;

map<ll,ll> mp;

ll pw(ll x,ll k,ll mod)

{

  ll ret=;while(k){if(k&)ret=ret*x%mod;x=x*x%mod;k>>=;}return ret;

}

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

{

  if(!b){x=;y=;return;}

  exgcd(b,a%b,y,x);y-=a/b*x;

}

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll solve3()

{

  A%=C;B%=C;

  if(!A)

    {

      if(!B)return ;else return -;

    }

  mp.clear();ll m=ceil(sqrt(C)),t;

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

    {

      if(!i){t=B%C;mp[t]=i;continue;}

      t=t*A%C;mp[t]=i;// if cover the previous one,it's correct

    }

  t=pw(A,m,C);ll ans=t;

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

    {

      if(mp[ans])return (i*m%C-mp[ans]%C+C)%C;//%C的位置

      ans=ans*t%C;

    }

  return -;

}

int main()

{

  scanf("%lld%lld",&T,&type);

  while(T--)

    {

      scanf("%lld%lld%lld",&A,&B,&C);

      if(type==)

      {

          B%=(C-);

          printf("%lld\n",pw(A,B,C));

      }

      if(type==)

      {

          ll g=gcd(A,C);//ll g

        if(B%g){printf("Orz, I cannot find x!\n");continue;}

        A/=g;C/=g;B/=g;

        exgcd(A,C,x,y);

        printf("%lld\n",(x*B%C+C)%C);//多%一个C

      }

      if(type==)

      {

          ll ans=solve3();

          if(ans==-)printf("Orz, I cannot find x!\n");

          else printf("%lld\n",ans);

      }

    }

  return ;

}