#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[50001]={0};
ll f(ll x,ll y,ll k)
{
	if (dp[k]>0) return dp[k];
	ll ans=x*y;
	if (x==1) return dp[k]=y;
	if (y==1) return dp[k]=x;
	for (ll i=2;i<=min(x,y);i++)
		ans-=f(x/i,y/i,k*i);
	return dp[k]=ans;
}
int main()
{
	ll x,y,k,T;
	cin>>T;
	while (T--){
		cin>>x>>y>>k;
		memset(dp,0,sizeof(dp));
		cout<<f(x/k,y/k,1)<<endl;
	}
}
/*
1 1 1 1 1 1
1 2 1 2 1 2
1 1 3 1 1 3
1 2 1 4 1 2
1 1 1 1 5 1
1 2 3 2 1 6
*/