#include <bits/stdc++.h>

using namespace std;

#define LL long long

LL n, k;

LL Ksm(LL a, LL b, LL p) {

    LL ret = ;

    while(b) {

        if(b & ) ret = ret * a % p;

        a = a * a % p;

        b >>= ;

    }

    return ret;

}

void Work1() {

    for(int i = ; i <= n; i ++) {

        LL y, z, p; cin >> y >> z >> p;

        cout << Ksm(y, z, p) << "\n";

    }

}

LL Exgcd(LL a, LL b, LL &x, LL &y) {

    if(b == ) {

        x = , y = ; return a;

    }

    LL g = Exgcd(b, a % b, x, y);

    LL tmpx = x; x = y; y = tmpx - a / b * y;

    return g;

}

void Work2() {

    for(int i = ; i <= n; i ++) {

        LL y, z, p; cin >> y >> z >> p;

        LL x, k;

        LL gcd = Exgcd(y, p, x, k);

        if(z % gcd) {

            puts("Orz, I cannot find x!"); continue;

        }

        LL r = z / gcd, d = p / gcd;

        x *= r;

        x = ((x % d) + d) % d;

        cout << x << "\n";

    }

}

map <LL, int> Map;

void Work3() {

    for(int i = ; i <= n; i ++) {

        LL y, z, p; cin >> y >> z >> p;

        // y ^ x = z (mod p)

        LL m = sqrt(p);

        if(m * m != p) m ++;

        // y ^ {im} = z * y ^ j (mod p)

        if(!(y % p)) {

            puts("Orz, I cannot find x!"); continue;

        }

        Map.clear();

        Map[z % p] = ;

        LL ans = z % p;

        for(int i = ; i <= m; i ++) {

            ans = (ans * y) % p;

            Map[ans] = i;

        }

        LL f = Ksm(y, m, p);

        bool flag = ;

        ans = ;

        for(int i = ; i <= m; i ++) {

            ans = ans * f % p;

            if(Map[ans]) {

                LL O = i * m - Map[ans];

                O = (O % p + p) % p;

                cout << O << "\n";

                flag = ;

                break;

            }

        }

        if(flag) {

            puts("Orz, I cannot find x!");

        }

    }

} 

int main() {

    cin >> n >> k;

    k ==  ? Work1() : (k ==  ? Work2() : Work3());

    return ;

}