#include<iostream> #include<map> #include<unordered_map> #include<ctime> using namespace std; #define int long long inline int read(){ int i=getchar(),r=0; while(i<'0'||i>'9')i=getchar(); while(i>='0'&&i<='9')r=(r<<1)+(r<<3)+(i^48),i=getchar(); return r; } const int N=100100,P=1000000007,inv2=(P+1)/2,B=2000; int prime[N],tot; bool tag[N]; int mu[N]; void euler(){ mu[1]=1; for(int i=2;i<N;i++){ if(!tag[i])mu[i]=-1,prime[++tot]=i; for(int j=1;j<=tot&&prime[j]*i<N;j++){ tag[prime[j]*i]=true; if(i%prime[j]==0)break; else mu[prime[j]*i]=-mu[i]; } } } int f[N]; inline int S(int n){return n*(n+1)/2%P;} unordered_map<int,int>F[N]; int F2[B][B]; inline int calc(int n,int m){ int res=0; for(int l=1;l<=n;l++){ if(l>m)break; int r=min(n/(n/l),m/(m/l)); res=(res+S(n/l)*S(m/l)%P*(f[r]-f[l-1]))%P; l=r; } return res; } inline int S2(int n,int m){ if(n<B&&m<B)return F2[n][m]; if(F[n].count(m))return F[n][m]; return F[n][m]=calc(n,m); } signed main(){ // freopen("gcdlcm.in","r",stdin); // freopen("gcdlcm.out","w",stdout); euler(); for(int i=1;i<N;i++)f[i]=mu[i]*i*i%P,f[i]=(f[i-1]+f[i])%P; for(int i=1;i<B;i++){ for(int j=i;j<B;j++){ F2[i][j]=S2(i,j); } } int T;cin>>T; while(T--){ int n=read(),m=read(),lim=read();if(n>m)swap(n,m); int ans=0; for(int g=1;g<=lim;g++){ // ans=(ans+S2(n/g,m/g)*g)%P; if(g>n||g>m)break; int r=min(lim,min(n/(n/g),m/(m/g))); ans=(ans+S2(n/g,m/g)*(S(r)-S(g-1)))%P; g=r; } printf("%lld\n",(ans+P)%P); } // cerr<<(clock()*1000/CLOCKS_PER_SEC); return 0; }