#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fst(ll x,ll y,ll mod){
	if (!y)return 1;
	if (y&1)return x*fst(x,y-1,mod)%mod;
	ll p=fst(x,y/2,mod);return p*p%mod;
}
int main(){
	freopen ("supercompute.in","r",stdin);
	freopen ("supercompute.out","w",stdout);
	int T,K;scanf("%d%d",&T,&K);
	while(T--){
		ll y,z,p;scanf("%lld%lld%lld",&y,&z,&p);
		y%=p;z%=p;
		if (K==1){
			printf("%lld\n",fst(y,z,p));
		}
		if (K==2){
			if (y%p==0){
				if (z==0)printf("0\n");
				else printf("Orz, I cannot find x!\n");
				continue;
			}
			printf("%lld\n",z*fst(y,p-2,p)%p);
		}
		if (K==3){
			if (z==1){
				printf("0\n");continue;
			}
			ll now=1;bool ok=0;
			for (int i=1;i<=5000000;i++){
				now=now*y%p;
				if (now==z){
					printf("%lld\n",i);ok=1;break;
				}
			}
			if (!ok)printf("Orz, I cannot find x!\n");
		}
	}
}