Rt 本机开-O2后 $\rm 6s$只有$40$分

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
#define P 1000000007
using namespace std;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int lcm(int x,int y){return x/gcd(x,y)*y;}
int uc[N],v[N],pm[N],tot,mu[N];
vector<int>u[N];
void prework(){
	int w=N-5;
	rep(i,1,w)rep(j,1,w){
		if(i*j>w)break;
		uc[i*j]++;
	}
	rep(i,1,w)uc[i]+=uc[i-1];
	mu[1]=1;
	rep(i,2,w){
		if(!v[i])mu[pm[++tot]=i]=-1;
		rep(j,1,tot){
			if(i*pm[j]>w)break;
			v[i*pm[j]]=1;
			if(i%pm[j]==0){mu[i*pm[j]]=0;break;}
			else mu[i*pm[j]]=-mu[i];
		}
	}
	rep(i,1,w)rep(j,1,w){
		if(i*j>w)break;
		if(mu[i]&&mu[i*j])u[i*j].push_back(i);
	}
}
inline int f(int x,int y){if(x>y)return 0;return uc[y/x];}
int a,b,c,in[N];bool rt[N];long long ans;
vector<pair<int,int> >ed;
vector<int>e[N];
inline void check(int x,int y,int z){
	//cout<<"ss "<<x<<" "<<y<<" "<<z<<endl;
	int i,j,k;long long tot=0;
	if(x!=y&&y!=z&&z!=x){
		i=x;j=y;k=z;tot+=1LL*f(lcm(i,j),a)*f(lcm(j,k),b)%P*f(lcm(i,k),c);
		i=x;j=z;k=y;tot+=1LL*f(lcm(i,j),a)*f(lcm(j,k),b)%P*f(lcm(i,k),c);
		i=y;j=x;k=z;tot+=1LL*f(lcm(i,j),a)*f(lcm(j,k),b)%P*f(lcm(i,k),c);
		i=y;j=z;k=x;tot+=1LL*f(lcm(i,j),a)*f(lcm(j,k),b)%P*f(lcm(i,k),c);
		i=z;j=x;k=y;tot+=1LL*f(lcm(i,j),a)*f(lcm(j,k),b)%P*f(lcm(i,k),c);
		i=z;j=y;k=x;tot+=1LL*f(lcm(i,j),a)*f(lcm(j,k),b)%P*f(lcm(i,k),c);
		ans+=tot*mu[x]*mu[y]*mu[z];return;
	}
	if(x==y&&y==z){ans+=1LL*f(x,a)*f(x,b)%P*f(x,c)*mu[x]*mu[x]*mu[x];return;}
	if(x==y)i=x,j=y,k=z;
	else if(y==z)i=y,j=z,k=x;
	else if(x==z)i=x,j=z,k=y;
	tot+=1LL*f(lcm(i,j),a)*f(lcm(j,k),b)%P*f(lcm(i,k),c);
	swap(j,k);tot+=1LL*f(lcm(i,j),a)*f(lcm(j,k),b)%P*f(lcm(i,k),c);
	swap(i,j);tot+=1LL*f(lcm(i,j),a)*f(lcm(j,k),b)%P*f(lcm(i,k),c);
	ans+=tot*mu[x]*mu[y]*mu[z]%P;
}
void solve(){
	scanf("%d%d%d",&a,&b,&c);
	int n=max(a,max(b,c));ans=0;ed.clear();
	rep(i,1,n)e[i].clear(),in[i]=0;
	rep(x,1,n)if(mu[x]){
		ed.push_back(make_pair(x,x));in[x]+=2;
		for(int i=0;i<(int)u[x].size();i++)
			for(int j=i+1;j<(int)u[x].size();j++)
				if(lcm(u[x][i],u[x][j])==x){
					//cout<<u[x][i]<<" "<<u[x][j]<<" "<<x<<" ss"<<endl;
					ed.push_back(make_pair(u[x][i],u[x][j])),
					in[u[x][i]]++,in[u[x][j]]++;
				}
	}
	register int x,y,i,j;
	for(i=0;i<(int)ed.size();i++){
		x=ed[i].first,y=ed[i].second;
		if(in[x]>in[y]||(in[x]==in[y]&&x>y))swap(x,y);
		e[x].push_back(y);
	}
	for(i=0;i<(int)ed.size();i++){
		x=ed[i].first,y=ed[i].second;
		//cout<<" uu "<<x<<" "<<y<<endl;
		for(j=0;j<(int)e[x].size();j++)rt[e[x][j]]=true;
		for(j=0;j<(int)e[y].size();j++)if(rt[e[y][j]])check(x,y,e[y][j]);
		for(j=0;j<(int)e[x].size();j++)rt[e[x][j]]=false;
	}
	printf("%lld\n",ans%1000000007);
}
int main(){
	int T;scanf("%d",&T);
	prework();
	while(T--)solve();
	return 0;
}
/*
2
100000 100000 100000
99999 99999 99999
*/