#include<map>

#include<set>

#include<ctime>

#include<cmath>

#include<stack>

#include<queue>

#include<string>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define lowbit(x) (x & (-x))

typedef unsigned long long int ull;

typedef long long int ll;

const double pi = 4.0*atan(1.0);

const int inf = 0x3f3f3f3f;

const int maxn = ;

const int maxm = ;

const int mod = 1e9+;

using namespace std;

ll n, m, p;

int T, tol;

ll phi[maxn];

ll inv[maxn];

ll f[maxn];

ll g[maxn];

void init() {

    memset(f, , sizeof f);

    memset(g, , sizeof g);

    memset(inv, , sizeof inv);

}

void handle() {

    for(int i=; i<maxn; i++)    phi[i] = i;

    for(int i=; i<maxn; i++) {

        if(phi[i] == i) {

            for(int j=i; j<maxn; j+=i) {

                phi[j] = phi[j] / i * (i-);

            }

        }

    }

}

int main() {

    handle();

    cin >> T;

    while(T--) {

        init();

        scanf("%I64d%I64d%I64d", &n, &m, &p);

        if(n > m)    swap(n, m);

        inv[] = ;

        for(int i=; i<=n; i++) inv[i] = (p - p/i) * inv[p%i] % p;

        for(int i=; i<=n; i++)    f[i] = (n/i) * (m/i) % p;

        for(int i=n; i>=; i--) {

            g[i] = f[i];

            for(int j=; i*j<=n; j++) {

                g[i] -= g[i*j];

                if(g[i] < )    g[i] += p;

            }

        }

        ll ans = ;

        for(int i=; i<=n; i++) {

            ans += i * g[i] % p * inv[phi[i]] % p;

            ans %= p;

        }

        printf("%I64d\n", ans);

    }

    return ;

}