#include <iostream>

using namespace std;
__int128_t n;

__int128_t pow(__int128_t a, __int128_t b) {
    __int128_t res = 1;
    while (b)
        if (b % 2) {
            res = (res * a) % n;
            b--;
        } else {
            a = (a * a) % n;
            b = b / 2;
        }
    return res;
}

__int128_t f(__int128_t x, __int128_t m) {
    if (m == 0) return 1;
    else if (m % 2) return f(x, m / 2) * (pow(x, (m + 1) / 2) + 1) % n;
    else return (f(x, m - 1) + pow(x, m)) % n;
}

int main() {
    int counter;
    cin >> counter;
    for (int c = 0; c < counter; ++c) {
        size_t x, m, nn;
        cin >> x >> m >> nn;
        n = __int128_t(nn);
        cout << (size_t) f(__int128_t(x), __int128_t(m)) << "\n";
    }
}