#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";
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKX19pbnQxMjhfdCBuOwoKX19pbnQxMjhfdCBwb3coX19pbnQxMjhfdCBhLCBfX2ludDEyOF90IGIpIHsKICAgIF9faW50MTI4X3QgcmVzID0gMTsKICAgIHdoaWxlIChiKQogICAgICAgIGlmIChiICUgMikgewogICAgICAgICAgICByZXMgPSAocmVzICogYSkgJSBuOwogICAgICAgICAgICBiLS07CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgYSA9IChhICogYSkgJSBuOwogICAgICAgICAgICBiID0gYiAvIDI7CiAgICAgICAgfQogICAgcmV0dXJuIHJlczsKfQoKX19pbnQxMjhfdCBmKF9faW50MTI4X3QgeCwgX19pbnQxMjhfdCBtKSB7CiAgICBpZiAobSA9PSAwKSByZXR1cm4gMTsKICAgIGVsc2UgaWYgKG0gJSAyKSByZXR1cm4gZih4LCBtIC8gMikgKiAocG93KHgsIChtICsgMSkgLyAyKSArIDEpICUgbjsKICAgIGVsc2UgcmV0dXJuIChmKHgsIG0gLSAxKSArIHBvdyh4LCBtKSkgJSBuOwp9CgppbnQgbWFpbigpIHsKICAgIGludCBjb3VudGVyOwogICAgY2luID4+IGNvdW50ZXI7CiAgICBmb3IgKGludCBjID0gMDsgYyA8IGNvdW50ZXI7ICsrYykgewogICAgICAgIHNpemVfdCB4LCBtLCBubjsKICAgICAgICBjaW4gPj4geCA+PiBtID4+IG5uOwogICAgICAgIG4gPSBfX2ludDEyOF90KG5uKTsKICAgICAgICBjb3V0IDw8IChzaXplX3QpIGYoX19pbnQxMjhfdCh4KSwgX19pbnQxMjhfdChtKSkgPDwgIlxuIjsKICAgIH0KfQ==