#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e6;

ll pow(ll a, ll b, ll p){
    ll ans = 1 % p;a = a % p;
    while(b){
        if(b & 1) ans = a * ans % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
ll exgcd(ll  a, ll  b, ll  &x, ll &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}
ll mod_reverse(ll a,ll n){
    ll x,y;
    ll d=exgcd(a,n,x,y);
    if(d==1) return (x%n+n)%n;
    else return -1;
}
ll exBSGS(ll a, ll b, ll p) { // a^x = b (mod p)
    a %= p; b %= p;
    if (a == 0) return b > 1 ? -1 : b == 0 && p != 1;
    ll c = 0, q = 1;
    while (1) {
        ll g = __gcd(a, p);
        if (g == 1) break;
        if (b == 1) return c;
        if (b % g) return -1;
        ++c; b /= g; p /= g; q = a / g * q % p;
    }
    static map<ll, ll> mp; mp.clear();
    ll m = ceil(sqrt(p));
    ll v = 1;
    for(int i = 1; i <= m; i++) {
        v = v * a % p;
        mp[v * b % p] = i;
    }
    for(int i = 1; i <= m ;i++) {
        q = q * v % p;
        auto it = mp.find(q);
        if (it != mp.end()) return i * m - it->second + c;
    }
    return -1;
}

ll t, k;
ll y,z,p;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin  >> t >> k;
    for(int i = 1; i <= t; i++){
        cin >> y >> z >> p;
        if(k == 1){
            cout<<pow(y,z,p)<<endl;
        }else if(k == 2){
            ll te = mod_reverse(y,p);
            if( te == -1){
                cout<<"Orz, I cannot find x!"<<endl;
            }else{
                cout<<te*z%p<<endl;
            }
        }else{
            ll te = exBSGS(y,z,p);
            if(te == -1){
                cout<<"Orz, I cannot find x!"<<endl;
            }else{
                cout<<te<<endl;
            }
        }
    }

    return 0;
}