#include <bits/stdc++.h> using namespace std; #define int long long const int maxn=1e5+10,mod=1e9+7; int n,m,a; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int prime[maxn],cnt; bool isprime[maxn]; int mu[maxn]; void init() { memset(isprime,true,sizeof(isprime)); isprime[1]=0,mu[1]=1; for(int i=2;i<=1e5;i++) { if(isprime[i]) prime[++cnt]=i,mu[i]=-1; for(int j=1;j<=cnt&&i*prime[j]<=1e5;j++) { isprime[prime[j]*i]=0; if(i%prime[j]==0) { mu[i*prime[j]]=0; break; } mu[i*prime[j]]=-mu[i]; } } } signed main() { // freopen("gcdlcm.in","r",stdin); // freopen("gcdlcm.out","w",stdout); ios::sync_with_stdio(false); init(); int T; cin>>T; while(T--) { cin>>n>>m>>a; if(n<m) swap(n,m); int ans=0; for(int i=1;i<=n;i++) { int t1=n/i,t2=m/i; int t=t1*(t1+1)/2%mod*(t2*(t2+1)/2%mod)%mod; int lst=0; for(int j=1;j<=a&&j*j<=i;j++) { if(i%j!=0) continue; ans+=t*(i*i/j%mod)%mod*mu[i/j]%mod,ans=(ans%mod+mod)%mod; if(j*j!=i&&i/j<=a) ans+=t*(i*i/(i/j)%mod)%mod*mu[i/(i/j)]%mod,ans=(ans%mod+mod)%mod; } } cout<<ans<<endl; } return 0; }