//100pts #include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair using namespace std; typedef long long ll; const int maxn=1e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,a,miu[maxn]; int tp,s1[maxn],s2[maxn]; int Miu(int x){ int w=0; for(int i=2;i*i<=x;++i)if(!(x%i)){ int c=0;while(!(x%i))x/=i,++c; if(c>=2)return 0;++w; }if(x!=1)++w; if(w&1)return -1; return 1; } void init(){ up(i,1,1e5)miu[i]=Miu(i); }int cal(int x){ return (x*1ll*(x+1)/2)%mod; } int q; struct nd { int n,m,id; }; vector<nd>v[maxn]; int res[maxn]; struct BIT { int t[maxn]; int lb(int x){return x&(-x);} void upd(int x,int v){for(;x<=1e5;x+=lb(x))(t[x]+=v)%=mod;} int qry(int x){int res=0;for(;x;x-=lb(x))(res+=t[x])%=mod;return res;} int g(int l,int r){return (qry(r)-qry(l-1)+mod)%mod;} }T; void slv(){ init(); q=read(); up(i,1,q){ int n=read(),m=read(),a=read(); if(n>m)swap(n,m); v[a].p_b((nd){n,m,i}); }up(i,1,1e5){ for(int j=i;j<=1e5;j+=i)if(miu[j/i]!=0){ if(miu[j/i]==1)T.upd(j,j*1ll*j/i%mod); else T.upd(j,mod-j*1ll*j/i%mod); } for(auto it:v[i]){ int l=1,r=0,n=it.n,m=it.m; while(l<=n){ r=min(n/(n/l),m/(m/l)); (res[it.id]+=cal(n/l)*1ll*cal(m/l)%mod*1ll*T.g(l,r)%mod)%=mod; l=r+1; } } }up(i,1,q)printf("%d\n",res[i]); } int main(){ //freopen("gcdlcm.in","r",stdin); //freopen("gcdlcm.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }