#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
long long t, k, y, z, p;
int log_mod(int a, int b, int n){
    if (b == 1) return 0;
    gp_hash_table <int, int>hash;
    int t = ceil(sqrt(n));
    long long z = 1;
    for (int i = 0; i < t; i++) {
        hash[b * z % n] = i;
        z = z * a % n;
    }
    int now = 1;
    for (int i = 1; i <= t; i++) {
        now = now * z % n;
        if (hash.find(now) != hash.end()) {
            return i * t - hash[now];
        }
    }
    return -1;
}
long long ksm(long long x, long long p, long long m){
    long long result = 1;
    while (p){
        if (p % 2 == 1){
            result = result * x % m;
        }
        p /= 2;
        x = x * x % m;
    }
    return result;
}
long long exgcd(long long a, long long b, long long &x, long long &y){
    if (b == 0){
        x = 1;
        y = 0;
        return a;
    }
    int ans = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return ans;
}
int main(){
    scanf("%lld%lld", &t, &k);
    while (t--){
        scanf("%lld%lld%lld", &y, &z, &p);
        if (k == 1){
            printf("%lld\n", ksm(y, z, p));
        } else if (k == 2){
            long long xn, yn;
            long long gcd = exgcd(y, p, xn, yn);
            if (z % gcd != 0){
                printf("Orz, I cannot find x!\n");
                continue;
            }
            printf("%lld\n", (xn * z % p + p) % p);
        } else if (k == 3){
            long long ans = log_mod(y, p, z);
            if (ans != -1) cout << ans << endl;
            else cout << "Orz, I cannot find x!" << endl;
        }
    }
    return 0;
}

疑惑，为什么别人都是#21没过，我k=3时就#21过了……