#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<int,int>
#define lowbit(i) i&-i
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
inline char gc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
#define gc getchar
inline ll read() {
    ll x = 0;
    char ch = gc();
    bool positive = 1;

    for (; !isdigit(ch); ch = gc())
        if (ch == '-')
            positive = 0;

    for (; isdigit(ch); ch = gc())
        x = x * 10 + ch - '0';

    return positive ? x : -x;
}
inline void write(ll a) {
    if (a < 0) {
        a = -a;
        putchar('-');
    }

    if (a >= 10)
        write(a / 10);

    putchar('0' + a % 10);
}
inline void writeln(ll a) {
    write(a);
    puts("");
}
inline void wri(ll a) {
    write(a);
    putchar(' ');
}
inline ull rnd() {
    ull ans = 0;
    For(i, 0, 5)ans = ans << 15 ^ rand();
    return ans;
}
ll mul(ll x, ll y, ll mod) {
    return ((x * y - (ll)((ld)x / mod * y + 0.5) * mod) + mod) % mod;
}
ll ksm(ll a, ll b, ll mod) {
    ll ans = 1;

    for (; b; b >>= 1) {
        if (b & 1)
            ans = mul(ans, a, mod);

        a = mul(a, a, mod);
    }

    return ans;
}
bool MR(ll n) {
    const int pr[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};

    if (n <= 1)
        return 0;

    int cnt = 0;
    ll d = n - 1;

    while (!(d & 1)) {
        cnt++;
        d >>= 1;
    }

    For(i, 0, 8) {
        if (n == pr[i])
            return 1;

        ll x = ksm(pr[i], d, n), p = x;
        For(i, 1, cnt) {
            x = mul(x, x, n);

            if (x == 1 && p != 1 && p != n - 1)
                return 0;

            p = x;
        }

        if (x != 1)
            return 0;
    }
    return 1;
}
ll f(ll x, ll c, ll n) {
    return (mul(x, x, n) + c) % n;
}
ll get(ll n) {
    const int B = 500;
    ll c = rand(), x = rand() % n, y = f(x, c, n), p = 1;

    while ((x != y) && ((p == 1))) {
        ll xx = x, yy = y, cj = 1;

        for (int i = 0; i <= B && x != y && cj; i++) {
            cj = mul(cj, abs(x - y), n);
            x = f(x, c, n);
            y = f(f(y, c, n), c, n);
        }

        ll t = __gcd(cj, n);

        if (t == 1)
            continue;
        else if (cj)
            return t;
        else {
            x = xx;
            y = yy;

            for (int i = 0; i <= B && x != y && p == 1; i++) {
                p = __gcd(abs(x - y), n);
                x = f(x, c, n);
                y = f(f(y, c, n), c, n);
            }
        }
    }

    return p;
}
map<ll, int> M;
void rho(ll n) {
    if (n == 1)
        return;

    if (MR(n)) {
        M[n]++;
        return;
    }

    ll t = get(n);

    while (t == 1 && t == n)
        t = get(n);

    rho(t);
    rho(n / t);
}
int ppp, jz;
ll ans, k, mod, pe[100], pp[100];
ll h(ll x) {
    return (x & 1) ? x : x / 2;
}
ll ycl[4][32000];
ll power(ll b) {
    ll ans = 1;
    For(i, 0, 3) {
        ans = ans * ycl[i][b % jz] % mod;
        b /= jz;
    }
    return ans;
}
ll g(ll x) {
    return power((x + 1) >> 1);
}
void dfs(int p, ll dq, ll s) {
    //cout<<p<<" "<<dq<<" "<<s<<endl;
    if (p > ppp) {
        //cout<<p<<" "<<dq<<" "<<s<<endl;
        ans = (ans + h(dq) % mod * g(dq) % mod * (s % mod + mod)) % mod;
        return;
    }

    if (pp[p] != 2)
        dfs(p + 1, dq, s * (1 - pp[p]));

    For(i, 1, pe[p]) {
        //cerr<<(i==pe[p])<<" "<<(1-pp[p])<<endl;
        dq *= pp[p];
        dfs(p + 1, dq, i == pe[p] ? s : s * (1 - pp[p]));
    }
}
int main() {
    int T = read();

    while (T--) {
        ll n = read();
        k = read(), mod = read();
        jz = pow(n, 0.25) + 3;
        For(i, 0, 3) {
            ll s;

            if (i)
                s = ycl[i - 1][jz];
            else
                s = k % mod;

            For(j, ycl[i][0] = 1, jz)ycl[i][j] = ycl[i][j - 1] * s % mod;
        }
        M.clear();
        rho(n);
        ans = ppp = 0;

        for (auto i : M) {
            pp[++ppp] = i.fi;
            pe[ppp] = i.se;
        }

        dfs(1, 1, 1);
        cout << ans << endl;
    }
}
/*
f(i)=\sum g(j)\mu(i/j)
1
9311702400 7367823578 1015387267
3 2 1000000005
3 3 1000000007
4 2 1000000009
4 3 1000000011
4 4 1000000013
5 5 1000000015
7 7 1000000017
9 9 1000000019

*/