#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll qpow(ll a,ll b){

    ll ans=;

    while(b){

        if(b&) ans=(ans*a);

        a=(a*a);

        b>>=;

    }

    return ans;

}

int main(){

    int T;scanf("%d",&T);

    while(T--){

        ll n,m,d;

        scanf("%lld %lld %lld",&n,&m,&d);

        vector<pair<ll,ll> > prs;

        vector<pair<ll,ll> >::iterator it;

        for(ll i=;i*i<=d;i++){

            if(d%i==){

                long long cnt=;

                while(d%i==){

                    d/=i;cnt++;

                }

                prs.push_back({i,cnt});

            }

        }

        ll res=;

        if(d!=) prs.push_back({d,});

        for(ll j=;j<=min(m,1LL*);j++){

            ll g=;

//            for(auto v:prs)

            for(it=prs.begin();it!=prs.end();it++)

            {

                g*=qpow( it->first,( it->second+j-)/j);

            }

            if(j==) res+=(m-)*(n/g);

            else res+=n/g;

        }

        printf("%lld\n",res);

    }

    return ;

}