#include<iostream> #include<map> #include<vector> #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; int t[N]; inline void add(int i,int k){while(i<N)t[i]=(t[i]+k)%P,i+=i&-i;} inline int get_sum(int i){int r=0;while(i)r=(r+t[i])%P,i-=i&-i;return r;} 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]; } } } inline int S(int n){return n*(n+1)/2%P;} struct offline{int n,m,id;}; vector<offline>ask[N]; int ans[N]; inline int get_sum(int l,int r){return (get_sum(r)-get_sum(l-1))%P;} signed main(){ // freopen("read.in","r",stdin); euler(); int T;cin>>T; for(int i=1;i<=T;i++){ int n=read(),m=read(); ask[read()].emplace_back((offline){n,m,i}); } for(int i=1;i<N;i++){ for(int j=1;j*i<N;j++)add(i*j,mu[j]*j*j%P*i%P); for(auto x:ask[i]){ int n=x.n,m=x.m; for(int l=1;l<=min(n,m);l++){ int r=min(n/(n/l),m/(m/l)); ans[x.id]=(ans[x.id]+S(n/l)*S(m/l)%P*get_sum(l,r))%P; l=r; } } } for(int i=1;i<=T;i++)printf("%lld\n",ans[i]); return 0; }