#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

void exgcd(LL a, LL b, LL &d, LL &x, LL &y) 
{
    if (b == 0) d = a, x = 1, y = 0;
    else
    {
        exgcd(b, a % b, d, y, x);
        y -= (a / b) * x;
    }
}

LL qpow(LL a, LL b, LL p)
{
    LL ans = 1 % p; a %= p;
    for (; b; b >>= 1)
    {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
    }
    return ans;
}

LL exBSGS(LL a, LL b, LL p)
{
    a %= p; b %= p; if (b == 1 || p == 1) return 0;
    LL ak = 1 % p, k = 0, d; 
    while ((d = __gcd(a, p)) != 1)
    {
        if (b % d) return -1;
        ak = ak * (a / d) % (p / d);
        k++; b /= d; p /= d;
        if (ak == b) return k;
    }
    LL m = ceil(sqrt(p)), am = 1;
    unordered_map<LL, LL> f;
    for (int j = 1; j <= m; j++) f[b * (am = am * a % p) % p] = j;
    for (int i = 1, t = ak; i <= m; i++) if (f.count(t = t * am % p)) return i * m - f[t] + k;
    return -1;
}

int main()
{
    LL A, B, X, Y, K, d;
    int T, op; scanf("%d%d", &T, &op);
    while (T--)
    {
        LL y, z, p; scanf("%lld%lld%lld", &y, &z, &p);
        if (op == 1) printf("%lld\n", qpow(y, z, p));
        else if (op == 2)
        {
            z = z % p;
            LL A, B, X, Y, K, d;
            A = y; B = p; K = z;
            exgcd(A, B, d, X, Y);
            if (K % d != 0) printf("Orz, I cannot find x!\n");
            else
            {
                LL dx = abs(B / d);
                X = X * (K / d);
                X = (X % dx + dx) % dx;
                printf("%lld\n", X);
            }
        }
        else if (op == 3)
        {
            y = y % p; z = z % p;
            LL A, B, P;
            A = y; B = z; P = p;
            LL X = exBSGS(A, B, P);
            if (X == -1) printf("Orz, I cannot find x!\n");
            else printf("%lld\n", X);
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
void exgcd(LL a,LL b,LL &d,LL &x,LL &y) 
{
    if(b==0)d=a,x=1,y=0;
    else
    {
        exgcd(b,a%b,d,y,x);
        y-=(a/b)*x;
    }
}
LL qpow(LL a,LL b,LL p)
{
	LL ans=1%p;a%=p;
	for(;b;b>>=1)
	{
		if(b&1)ans=ans*a%p;
		a=a*a%p;
	}
	return ans;
}
LL exBSGS(LL a,LL b,LL p)
{
	a%=p;b%=p;if(b==1 || p==1) return 0;
	LL ak=1%p,k=0,d; 
	while( (d=__gcd(a,p) )!=1 )
    {
        if(b%d)return -1;
        ak=ak*(a/d)%(p/d);
		k++;b/=d;p/=d;
		if(ak==b) return k;
    }
	LL m=ceil(sqrt(p)),am=1;
	unordered_map<LL,LL>f;
	for(int j=1;j<=m;j++)f[b*(am=am*a%p)%p]=j;
	for(int i=1,t=ak;i<=m;i++)if( f.count(t=t*am%p) )return i*m-f[t]+k;
	return -1;
}
int main()
{
    LL A,B,X,Y,K,d;
    int T,op;scanf("%d%d",&T,&op);
	while(T--)
	{
		LL y,z,p;scanf("%lld%lld%lld",&y,&z,&p);
	    if(op==1) printf("%lld\n", qpow(y,z,p) );
		else if(op==2)
		{
			z=z%p;
			LL A,B,X,Y,K,d;
			A=y;B=p;K=z;
			exgcd(A,B,d,X,Y);
			if(K%d!=0) printf("Orz, I cannot find x!\n");
			else
			{
				LL dx=abs(B/d);
				X=X*(K/d);
				X=(X%dx+dx)%dx;
				printf("%lld\n",X);
			}
		}
		else if(op==3)
		{
			y=y%p;z=z%p;
			LL A,B,P;
			A=y;B=z;P=p;
			LL X=exBSGS(A,B,P);
			if(X==-1)printf("Orz, I cannot find x!\n");
			else printf("%lld\n",X);
		}
	}
    return 0;
}