#include<bits/stdc++.h> using namespace std; const int N=1e5+20,INF=1e9+10,mod=1e9+7; int n,m,a; int mu[N];bool isp[N]; vector<int> p,d[N]; void init(){ mu[1]=1; for(int i=2;i<=N-5;i++){ if(!isp[i]) p.push_back(i),mu[i]=-1; for(auto j:p){ if(i*j>N-5) break; isp[i*j]=1; if(i%j==0) break; mu[i*j]=-mu[i]; } }for(int i=1;i<=N-5;i++){ for(int j=i;j<=N-5;j+=i){ d[j].push_back(i); } } }int plu(int a,int b){ a+=b;if(a>=mod) a-=mod;return a; }int miu(int a,int b){ a-=b;if(a<0) a+=mod;return a; }int LM=N-10; struct BIT{ int T[N]; int lb(int x){ return x&(-x); }void upd(int x,int v){ for(int i=x;i<=LM;i+=lb(i)) T[i]=plu(T[i],v); }int qry(int x){ int res=0; for(int i=x;i>0;i-=lb(i)) res=plu(res,T[i]); return res; } }bit; void add(int x){ for(int i=x;i<=LM;i+=x){ int dt=1ll*i*i/x%mod*(mod+mu[i/x])%mod; //if(i<100)cout<<i<<' '<<dt<<' '<<"upd"<<endl; bit.upd(i,dt); } }int S(int x){ return (1ll*(1+x)*x/2)%mod; } int calc(int n,int m){ int res=0; int l=1;int r; while(l<=min(n,m)){ r=min(n/(n/l),m/(m/l)); res=plu(res,1ll*miu(bit.qry(r),bit.qry(l-1))*S(n/l)%mod*S(m/l)%mod); //cout<<res<<' '<<l<<' '<<miu(bit.qry(r),bit.qry(l-1))<<endl; l=r+1; }return res; }struct qid{ int id,n,m,a; }Q[N]; int A[N]; bool cmp(qid a,qid b){ return a.a<b.a; }int t; void slv(){ int t;cin>>t;init(); for(int i=1;i<=t;i++){ Q[i].id=i;cin>>Q[i].n>>Q[i].m>>Q[i].a; }int it=0;sort(Q+1,Q+t+1,cmp); for(int i=1;i<=t;i++){ while(it<Q[i].a) it++,add(it); A[Q[i].id]=calc(Q[i].n,Q[i].m); }for(int i=1;i<=t;i++){ cout<<A[i]<<endl; } } int main(){ slv(); return 0; }