/* http://www.cnblogs.com/karl07/ */

 #include <cstdlib>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <map>

 #include <algorithm>

 using namespace std;

 #define LL long long

 int T,K;

 LL a,b,p;

 LL Q_tim(LL x,LL y,LL p){

     LL ans=;

     while (y){

         if (y&) ans=(ans+x)%p;

         x=(x+x)%p;

         y=(y>>);

     }

     return ans;

 }

 LL Q_pow(LL x,LL y,LL p){

     LL ans=;

     while (y){

         if (y&) ans=ans*x%p;

         x=x*x%p;

         y=(y>>);

     }

     return ans;

 }

 void ex_gcd(LL a,LL b,LL &x,LL &y,LL &gcd){

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

     ex_gcd(b,a%b,y,x,gcd);

     y-=x*(a/b);

 }

 void p2(LL a,LL b,LL p){

     LL x,y,gcd,g,ans=p+;

     ex_gcd(a,p,x,y,gcd);

     if (b%gcd!=){ puts("Orz, I cannot find x!"); return;}

     ex_gcd(a/gcd,p/gcd,x,y,g);

     x=x*(b/gcd)%p;

     x=(x+p)%p;

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

 }

 void BSGS(LL a,LL b,LL p){

     if ((a== && b!=) || (a== && b!=)) { puts("Orz, I cannot find x!"); return;}

     LL sz=(LL)ceil(sqrt(p)),inv,e=;

     map<LL,LL> x;

     x.clear();

     x[]=;inv=Q_pow(Q_pow(a,sz,p),p-,p);

     for (int i=;i<sz;i++) {e=Q_tim(e,a,p); if (!x.count(e)) x[e]=i;}

     for (int i=;i<sz;i++) {

         if (x.count(b)) {printf("%lld\n",i*sz+x[b]); return;}

         b=Q_tim(b,inv,p);

     }

     puts("Orz, I cannot find x!");

 }

 int main(){

     scanf("%d%d",&T,&K);

     for (int i=;i<=T;i++){

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

         if (K==) printf("%lld\n",Q_pow(a%p,b,p));

         if (K==) p2(a%p,b%p,p);

         if (K==) BSGS(a%p,b%p,p);

     }

     return ;

 }