#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 LIM=2200; int G[LIM+10][LIM+10]; int igcd[LIM+10][LIM+10]; int U[LIM+10][LIM+10]; const int M=1e9+7; int cnt=0; //unordered_map<int,int>ANSG[100020]; inline void add(int &x,int y){ x+=y; if(x>=M)x-=M; } 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 int g(int x,int y){ if(x<=LIM&&y<=LIM)return G[x][y]; if(x>y)swap(x,y); int res=0; //if(ANSG[x].count(y))return ANSG[x][y]; for(int l=1,r;l<=x;l=r+1){ cnt++; r=min(x/(x/l),y/(y/l)); res=(res+1ll*(s2mu[r]-s2mu[l-1])*S(x/l)%M*S(y/l))%M; } return res; } inline int gcd(int a,int b){ if(a>b)swap(a,b); if(b<=LIM)return igcd[a][b]; return b==0?a:gcd(b,a%b); } bitset<100300> p; vector<int>P; 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]=(s2mu[i-1]+1ll*mu[i]*i%M*i%M)%M; } mt19937 RD(time(0)); signed main(){ ios::sync_with_stdio(0); freopen("gcdlcm.in","r",stdin); freopen("gcdlcm.out","w",stdout); init(); for(int i=1;i<=LIM;i++) igcd[0][i]=i; for(short i=1;i<=LIM;i++) for(short j=i;j<=LIM;j++){ igcd[i][j]=igcd[j%i][i]; } for(short i=1;i<=LIM;i++) for(short j=1;j<i;j++) igcd[i][j]=igcd[j][i]; for(int i=1;i<=LIM;i++) for(int j=1;j<=LIM;j++){ add(G[i][j],G[i-1][j]); add(G[i][j],G[i][j-1]); add(G[i][j],M-G[i-1][j-1]); if(igcd[i][j]==1) add(G[i][j],i*j); } //return 0; int t=1e4; cin>>t; while(t--){ cin>>n>>m>>a; //n=1e5-5000,m=1e5,a=1e5; //n=RD()%90000+100; //m=RD()%90000+100; //a=RD()%90000+100; int res=0; //cout<<g(n,m)<<" "<<fg(n,m)<<endl; //for(int i=1;i<=a;i++) // res=(res+i*g(n/i,m/i)%M)%M; if(n>m)swap(n,m); for(int l=1,r;l<=n&&l<=a;l=r+1){ r=min(n/(n/l),m/(m/l)); int lim=min(r,a); res=(res+1ll*S(l,lim)*g(n/l,m/l)%M)%M; } cout<<(res%M+M)%M<<endl; } cout.flush(); return 0; }