#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <cmath>

using namespace std;

typedef long long ll;

int T, k;

ll quick_pow (ll a, ll b, ll p) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        b >>= 1, a = a * a % p;
    }
    return res;
}

ll exgcd (ll a, ll b, ll &x, ll &y) {
    if (b == 0) {x = 1, y = 0; return a;}
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

ll BSGS (ll a, ll b, ll p) {
    if (1 % p == b % p) return 0;
    ll k = sqrt(p) + 1;
    unordered_map <ll, ll> hash;
    for (ll y = 0, ay = 1; y < k; y ++ , ay = ay * a % p) hash[b * ay % p] = y;
    ll ak = 1;
    for (int i = 1; i <= k; i ++ ) ak = ak * a % p;
    for (ll i = 1, akx = ak % p; i <= k; i ++ , akx = akx * ak % p) if (hash.count(akx)) return k * i - hash[akx];
    return -1;
}

int main () {
    ll y, z, p, x, xx;
    cin >> T >> k;
    while (T -- ) {
        cin >> y >> z >> p;
        if (k == 1) cout << quick_pow(y, z, p) << '\n';
        if (k == 2) {
            ll d = exgcd(y, p, x, xx);
            p /= d;
            if (z % d == 0) cout << (x * (z / d) % p + p) % p << '\n';
            else cout << "Orz, I cannot find x!" << '\n';
        }
        if (k == 3) {
            ll res = BSGS(y % p, z % p, p);
            if (res == -1) cout << "Orz, I cannot find x!" <<'\n';
            else cout << res <<'\n';
        }
    }
    return 0;
}

input

10 3
1000052719 255392610 79791109
146324954 14948940 73162477
703874049 508100543 1037977027
260580983 889231132 496040033
691085033 402703206 539487719
752770845 539141408 817774367
974839853 763383053 22685989
855218194 362010502 198721379
900451466 1064373182 697990169
13892212 176820695 856980737

ans:

6834829
Orz, I cannot find x!
Orz, I cannot find x!
Orz, I cannot find x!
156564190
332099841
10685557
3418253
Orz, I cannot find x!
288589667

my output:

6834829
1
Orz, I cannot find x!
Orz, I cannot find x!
156564190
332099841
10685557
3418253
Orz, I cannot find x!
288589667