#include<bits/stdc++.h> using namespace std; #define int long long #define ll long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=100010,N=100000,Mod=1000000007; int n,m,q,ans[MAXN],mu[MAXN],fl[MAXN],p[MAXN],cnt; struct node{ int id,x,y,p; bool operator<(const node&G)const{ return p<G.p; } }a[MAXN]; void Mu(int x){ mu[1]=1; for(int i=2;i<=x;i++){ if(!fl[i])p[++cnt]=i,mu[i]=-1; for(int j=1;j<=cnt&&p[j]*i<=x;j++){ fl[p[j]*i]=1; if(i%p[j]==0){ mu[i*p[j]]=0; break; } mu[i*p[j]]=-mu[i]; } } } struct treearray{ int C[MAXN]; int lb(int x){return x&(-x);} void upd(int x,int y){for(int i=x;i<=N;i+=lb(i))C[i]+=y,C[i]=(C[i]%Mod+Mod)%Mod;} int qry(int x){int res=0;for(int i=x;i>=1;i-=lb(i))res+=C[i],res=(res%Mod+Mod)%Mod;return res;} int qry(int l,int r){return qry(r)-qry(l-1);} }T; void slv(){ q=read(); Mu(N); for(int i=1;i<=q;i++){ a[i].x=read(),a[i].y=read(),a[i].p=read(),a[i].id=i; } sort(a+1,a+q+1); int it=1; for(int i=1;i<=q;i++){ while(it<=a[i].p){ for(int j=it;j<=N;j+=it)T.upd(j,j/it*j%Mod*mu[j/it]%Mod); it++; } n=a[i].x,m=a[i].y; for(int l=1,r=1;l<=min(m,n);l=r+1){ r=min(n/(n/l),m/(m/l)); int x=n/l,y=m/l; ans[a[i].id]+=(x*(x+1)/2)%Mod*(y*(y+1)/2)%Mod*T.qry(l,r)%Mod; ans[a[i].id]%=Mod; } } for(int i=1;i<=q;i++){ printf("%lld\n",(ans[i]+Mod)%Mod); } } signed main(){ slv(); // system("grep VmPeak /proc/$PPID/status"); return 0; }