#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e6+5;
ll qpow(ll a, ll b, ll p){
	ll res = 1;
	while (b){
		if (b & 1) res = a * res % p;
		a = a * a % p;
		b >>= 1;
	}
	return res % p;
}
ll exgcd(ll a, ll b, ll &x, ll &y){
	if (b == 0){
		x = 1, y = 0;
		return a;
	}
	exgcd(b, a % b, x, y);
	ll k = x;
	x = y;
	y = k - a / b * y;
}
void sub1(ll a, ll b, ll p){
	a %= p;
	cout << qpow(a, b, p) << '\n';
}
void sub2(ll a, ll b, ll p){
	a %= p;
	b %= p;
	if (a == 0 && b != 0){
		cout << "Orz, I cannot find x!\n";
	}
	ll x = 0, y = 0;
	ll d = exgcd(a, p, x, y);
	x = (x + p) % p;
	x = (x * b) % p;
	cout << x << '\n';
}
ll bsgs(ll a, ll b, ll p){
	map<ll, ll> mp;
	mp.clear();
	ll sqrtp = sqrt(p) + 1;
	ll c = 1;
	for (ll j = 1;j <= sqrtp;j++){
		c = c * a % p;
		mp[b * c % p] = j;
	} 
	ll a1 = c;
	for (ll i = 1;i <= sqrtp;i++){
		if (mp[a1]) return i * sqrtp - mp[a1];
		a1 = a1 * c % p;
	}
	return -1;
}
void sub3(ll a, ll b, ll p){
	a %= p;
	if (a == 0 && b == 0){
		cout << "1\n";
		return;
	} 
	if (a == 0 && b != 0){
		cout << "Orz, I cannot find x!\n";
		return;
	}
	ll t = bsgs(a, b, p);
	if (t == -1) cout << "Orz, I cannot find x!\n";
	else cout << t << '\n';
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int t, k;
	cin >> t >> k;
	while (t--){
		ll a, b, p;
		cin >> a >> b >> p;
		if (k == 1) sub1(a, b, p);
		else if (k == 2) sub2(a, b, p);
		else{
			sub3(a, b, p);	
		}
	}
	return 0;
}