#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define endl "\n" int mu[100300]; int s2mu[100300]; int n,m,a; const int M=1e9+7; int cnt=0; inline void add(int &x,int y){ x+=y; if(x>=M)x-=M; if(x<0)x+=M; if(x>=M)x-=M; if(x<0)x+=M; if(x>=M)x-=M; if(x<0)x+=M; } bitset<100300> p; vector<int>P; inline int S(int n){ if(n<0)return 0; return 1ll*n*(n+1)/2%M; } inline int S(int l,int r){ return (S(r)-S(l-1))%M; } inline void init(){ //memset(p,1,sizeof(p)); p.set(); p[1]=0;mu[1]=1; for(int i=2;i<=1e5;i++){ if(p[i]){ P.push_back(i); mu[i]=-1; } for(int x:P){ if(1ll*x*i>1e5)break; p[1ll*x*i]=0; if(i%x==0){ mu[x*i]=0; break; } mu[1ll*x*i]=-mu[i]; } } for(int i=1;i<=1e5;i++) s2mu[i]=1ll*mu[i]*i%M*i%M; } mt19937 RD(time(0)); struct ask{int n,m,a,id;}A[200300]; int ANS[200300]; int t[200300]; inline int lb(int x){return x&-x;} inline void mod(int x,int k){ while(x<=1e5){ add(t[x],k); x+=lb(x); } } inline int g(int x){ int res=0; while(x){ add(res,t[x]); x-=lb(x); } return res; } inline bool cmp(ask A,ask B){ return A.a<B.a; } inline void ins(int x){ for(int p=x;p<=1e5;p+=x) mod(p,p*p/x%M*mu[p/x]%M); } inline int g(int l,int r){ return (g(r)-g(l-1)+M)%M; } signed main(){ ios::sync_with_stdio(0); //freopen("gcdlcm.in","r",stdin); //freopen("gcdlcm.out","w",stdout); init(); int t; cin>>t; for(int i=1;i<=t;i++) cin>>A[i].n>>A[i].m>>A[i].a,A[i].id=i; sort(A+1,A+t+1,cmp); int now=0; for(int i=1;i<=t;i++){ while(now<A[i].a){ now++; ins(now); } int n=A[i].n,m=A[i].m; for(int l=1,r;l<=n&&l<=m;l=r+1){ r=min(n/(n/l),m/(m/l)); add(ANS[A[i].id],S(n/l)*S(m/l)%M*g(l,r)%M); } } for(int i=1;i<=t;i++) cout<<ANS[i]<<endl; cout.flush(); return 0; }