#include <iostream>
#include <stdio.h>

using namespace std;

int phi(int n) {
    int res = 1;
    for (int d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            int p = 1;
            while (n % d == 0) {
                n /= d;
                p *= d;
            }

            res *= (p - p / d);
        }
    }

    res *= (n - 1);

    return res;
}

int powmod(int a, int p, int n) {
    int res = 1;
    for (int x = a; p > 0; p /= 2) {
        if (p % 2 == 1) res = (res * x) % n;
        x = (x * x) % n;
    }

    return res;
}

int main() {
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int e, n, c;
        cin >> e >> n >> c;

        // if (c < 0) {
        //  c = n - c;
        // }

        int phin = phi(n);
        int d = powmod(e, phi(phin) - 1, phin);
        cout << powmod(c, d, n) << endl;
    }
}