$$d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$$

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[gcd(i,j)=1]$$

$x$ 和 $y$ 我们扔到前面去枚举，后面来计算它们对它们的倍数做出的贡献。

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[gcd(i,j)=1]$$

$$=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[gcd(i,j)=1]$$

$$f(x)=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[gcd(i,j)=k]$$

$$g(k)=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[k|gcd(i,j)]$$

$$g(k)=\sum_{k|d} f(d)$$

$$f(k)=\sum_{k|d}\mu(\frac{d}{k})g(d)$$

$$f(1)=\sum_{d=1}^{n}\mu(d)g(d)$$

$$g(k)=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[k|gcd(i,j)]$$

$$g(k)=\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\frac{n}{xk}\rfloor\lfloor\frac{m}{yk}\rfloor$$

$$s(k)=\sum_{i=1}^{k}\lfloor\frac{k}{i}\rfloor$$

$$g(k)=s(n/k) \cdot s(m/k)$$

#### Code:

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>

#define ll long long
#define min(x,y) ((x)<(y)?(x):(y))

const int N=5e4+2;
const int inf=1e9+9;

int T,n,m,cnt;
int mui[N],vis[N],prime[N];
ll s[N];

inline void _pre_mui(){
mui[1]=1;
for(int i=2;i<=N;++i){
if(!vis[i])prime[++cnt]=i,mui[i]=-1;
for(int j=1;j<=cnt;++j){
if(i*prime[j]>5e4)break;
vis[i*prime[j]]=1;
if(!(i%prime[j])){mui[i*prime[j]]=0;break;}
mui[i*prime[j]]=-mui[i];
}
}
for(int i=1;i<=N;++i)mui[i]+=mui[i-1];
for(int x=1;x<=N;++x){//实际上这里是 O(n sqrt(n))，不过影响不大。
ll res=0;
for(int l=1,r=0;l<=x;l=r+1)
r=(x/(x/l)),res+=1ll*(r-l+1)*(x/l);
s[x]=res;
}return;
}

inline ll solve(int n,int m){
ll ans=0;
if(n>m)n^=m^=n^=m;
for(int l=1,r=0;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
ans+=1ll*(mui[r]-mui[l-1])*s[n/l]*s[m/l];
}return ans;
}

int main(){
_pre_mui();
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
printf("%lld\n",solve(n,m));
}return 0;
}


QAQ