#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int mpow(ll a, ll b, ll p) {

	ll r=1; a%=p;

	while(b) { if(b&1) r=((ll)r*a)%p; a=((ll)a*a)%p; b>>=1; }

	return r;

}

void gcd(ll a, ll b, ll &d, ll &x, ll &y) {

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

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

}

void ni(ll a, ll b, ll p) {

	ll d, x, y, t;

	gcd(a, p, d, x, y); if(b%d) { puts("Orz, I cannot find x!"); return; }

	t=p/d;

	while(x<0) x+=t;

	while(x>=t) x-=t;

	printf("%lld\n", (x*b)%p);

}

map<int, int> s;

void bsgs(ll y, ll z, ll p) {

	y%=p; z%=p;

	if(z==1) { puts("0"); return; }

	if(!y && !z) { puts("1"); return; }

	if(!y) { puts("Orz, I cannot find x!"); return; }

	s.clear();

	int m=sqrt(p+0.5), t=1, w=y;

	for(int i=0; i<m; ++i) s[((ll)z*t)%p]=i, t=((ll)t*w)%p;

	w=mpow(y, m, p); y=1; t=(p-1)/m+1; bool flag=1;

	for(int i=0; i<=t; ++i) if(s.count(y)) { printf("%lld\n", (ll)m*i-s[y]); flag=0; break; } else y=((ll)y*w)%p;

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

}

int main() {

	int z, y, p, c, T;

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

	while(T--) {

		scanf("%d%d%d", &y, &z, &p);

		if(c==1) printf("%d\n", mpow(y, z, p));

		else if(c==2) ni(y, z, p);

		else bsgs(y, z, p);

	}

	return 0;

}