rt,Wa on #2,#5-10

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
inline int read(){
	int x=0;bool f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=0;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return f?x:-x;
}
const int maxn=100000,maxa=1000000001ll,mod=2147483648;
struct qry{
	int n,m,a,id;
	bool operator <(qry x) const{
		return a^x.a?a<x.a:id<x.id;
	}
}q[40005];
int mu[maxn+5],ans[maxn+5],prime[maxn],a[maxn+5],cnt,Q,t[maxn+5];
bitset<100005> vis;
pair<int,int> p[100005];
inline int Pow(int x,int y){
	int res=1;
	while(y){
		if(y&1){
			res*=x;
			if(res>=maxa) return maxa; 
		}
		x*=x;
		if(x>=maxa) return maxa;
		y>>=1;
	}
	return res;
}
inline void Add(int x,int val){
	for(;x<=maxn;x+=(x&(-x))) t[x]=(t[x]+val)%mod;
}
inline int sum(int x){
	int res=0;
	for(;x;x-=(x&(-x))) 
		(res+=t[x])%=mod;
	return res;
}
inline int query(int x,int y){
	if(x>y) swap(x,y);
	int l=1,r,res=0;
	while(l<=x){
		r=min(x/(x/l),y/(y/l));
		(res+=(x/l)*(y/l)%mod*(sum(r)-sum(l-1))%mod)%=mod;
		l=r+1;
	}
	return (res+mod)%mod;
}
signed main(){
	mu[1]=p[1].first=p[1].second=1;
	for(int i=2;i<=maxn;i++){
		if(!vis[i]) prime[++cnt]=i,mu[i]=-1,p[i].first=i+1;
		for(int j=1;j<=cnt&&prime[j]<=maxn/i;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]) p[i*prime[j]].first=min(p[i].first*p[prime[j]].first,maxa),mu[i*prime[j]]=-mu[i];
			else{
				int k=i,l=1;
				while(!(k%prime[j])) k/=prime[j],l++;
				p[i*prime[j]].first=min(maxa,p[i].first+Pow(prime[j],l)*p[k].first);
				break;
			}
		}
		p[i].second=i;
	}
//	for(int i=1;i<=1145;i++)
//		printf("%d\n",p[i].first);
	Q=read();
	for(int i=1;i<=Q;i++) 
		q[i].n=read(),q[i].m=read(),q[i].a=read(),q[i].id=i;
	sort(q+1,q+Q+1);
	sort(p+1,p+maxn+1);
	for(int j=0,i=1;i<=Q;i++){
		while(j<maxn&&p[j+1].first<=q[i].a){
			++j;
			for(int k=p[j].second;k<=maxn;k+=p[j].second)
				if(mu[k/p[j].second])
					Add(k,(mu[k/p[j].second]*p[j].first+mod)%mod);
		}
		if(j)
			ans[q[i].id]=query(q[i].n,q[i].m);
	}
	for(int i=1;i<=Q;i++)
		printf("%llu\n",ans[i]);
	return 0;
}