HDU6390

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e6+7;

int tot;
int pri[N];
int phi[N];
int mu[N];
bool mark[N];

inline void pre(int n){
    mu[1]=phi[1]=1;
    for(int i=2;i<=n;++i){
        if(!mark[i])pri[++tot]=i,phi[i]=i-1,mu[i]=-1;
        for(int j=1,tmp;j<=tot;++j){
            if((tmp=i*pri[j])>n)break;
            mark[tmp]=1;
            if(i%pri[j]){
                phi[tmp]=phi[i]*phi[pri[j]];
                mu[tmp]=-mu[i];
            }
            else {
                phi[tmp]=phi[i]*pri[j];
                mu[tmp]=0;
                break;
            }
        }
    }
}

int inv[N];

int n,m,p;

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int T;r(T);
    pre(1e6);
    while(T--){
        r(n),r(m),r(p);
        if(n>m)swap(n,m);
        inv[1]=1;
        for(int i=2;i<=n;++i){
            inv[i]=(ll)(p-p/i)*inv[p%i]%p;
        }
        ll ans=0;
        for(int i=1;i<=n;++i){
            int t1=m/i,t2=n/i;
            int t=min(t1,t2);
            ll sum=0;
            for(int j=1;j<=t;++j){
                sum+=(ll)mu[j]*(t1/j)*(t2/j)%p;
            }
            sum=(sum%p+p)%p;
            ans+=(ll)i*inv[phi[i]]%p*sum%p;
        }
        printf("%lld\n",ans%p);
    }
    return 0;
}