#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
int quick_pow(int x,int y,int mod){
	int ans = 1;
	while(y){
		if(y & 1)
			ans = ans * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ans;
}
int exgcd0(int a,int b,int &x,int &y) {
	if(b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	int ret = exgcd0(b,a % b,x,y);
	int tmp = x;
	x = y;
	y = tmp - (a / b) * y;
	return ret;
}
int linear_equation(int a,int b,int c) {
	int x,y;
	int z = exgcd0(a,b,x,y);
	if(c % z)
		return -INF;
	int k = c / z;
	x *= k;
	y *= k;
    return (x % b + b) % b;
}
map<int,int> Hash;
struct triple{
	int x,y,z;
	triple(int _x_,int _y_,int _z_){x = _x_;y = _y_;z = _z_;}
};
triple exgcd(int a,int b){
	if(b == 0)
		return triple(1,0,a);
	triple last = exgcd(b,a % b);
	return triple(last.y,last.x - a / b * last.y,last.z);
}
int BSGS(int b,int n,int p){
	if(p == 1 || n == 1)
    	return 0;
	int m = (int)sqrt(p);
	Hash.clear();
	int base = 1;
    //预处理
    
	for(int i = 0;i < m;i++){
		Hash[base] = i;
		base = base * b % p;
	}
	int d = 1;
	for(int i = 0;i < m;i++){
		triple res = exgcd(d,p);
		int C = p / res.z;
		res.x = (res.x * n / res.z % C + C) % C;
		int j = Hash[res.x];
		if(j)//如果b^j mod p存在，返回 
			return i * m + j;
		d = d * base % p;//此时base的值为b^m
	}
	return -INF;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int t,k;
	cin >> t >> k;
	while(t--){
		int y,z,p;
		cin >> y >> z >> p;
		if(k == 1)
			cout << quick_pow(y,z,p) << '\n';
		if(k == 2){
			int ans = linear_equation(y,p,z);
			if(ans == -INF)
				cout << "Orz, I cannot find x!\n";
			else
				cout << ans << '\n';
		}
		if(k == 3){
			y %= p;z %= p;
			int ans = BSGS(y,z,p);
			//cout << "同余方程 " << y << " ^ x" << " = " << z << "(mod " << p << ") 的结果是";
			if(ans == -INF)
				cout << "Orz, I cannot find x!\n";
			else
				cout << ans << '\n';
		}
	}
	return 0;
}