#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=5e4+10;
LL prime[N],tot,mu[N],s[N];
bool v[N];
LL n,m,d,p,q,g,ans;
signed main() {
	s[1]=mu[1]=1;
	for(LL i=2; i<N; i++) {
		if(!v[i]) {prime[++tot]=i; mu[i]=-1;}
		s[i]=s[i-1]+mu[i];
		for(LL j=1; j<=tot&&i*prime[j]<N; j++) {
			v[i*prime[j]]=1;
			if(i%prime[j]==0) break;
			mu[i*prime[j]]=-mu[i];
		}
	}
	scanf("%lld",&g);
	for(; g; g--) {
		ans=0;
		scanf("%lld%lld%lld",&n,&m,&d);
		p=n/d; q=m/d;
		if(p>q) swap(p,q);
		for(LL l=1,r; l<=p; l=r+1) {
			r=p/(p/l);
			ans+=(s[r]-s[l-1])*(p/l)*(q/l);
		}
		printf("%lld\n",ans);
	}
	return 0;
}