$\color{green}{前置知识}$

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

$\color{green}{推式子}$

$$ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^md(ij)&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[(i,j)=1]\\\\ &=\sum_{x=1}^n\sum_{y=1}^m[(x,y)=1]\sum_{i=1}^{\lfloor\frac nx\rfloor}\sum_{j=1}^{\lfloor\frac ny\rfloor}\\\\ &=\sum_{x=1}^n\sum_{y=1}^m[(x,y)=1]\lfloor\frac nx\rfloor\lfloor\frac my\rfloor\\\\ &=\sum_{x=1}^n\sum_{y=1}^m\sum_{d|(x,y)}\mu(d)\lfloor\frac nx\rfloor\lfloor\frac my\rfloor\\\\ &=\sum_{d=1}^n\mu(d)\sum_{x=1}^{\lfloor\frac nd\rfloor}\sum_{y=1}^{\lfloor\frac md\rfloor}\lfloor\frac n{xd}\rfloor\lfloor\frac m{yd}\rfloor\\\\ &=\sum_{d=1}^{n}\mu(d)g(\lfloor\frac nd\rfloor)g(\lfloor\frac md\rfloor)\\\\ &其中g(x)=\sum_{i=1}^x\lfloor\frac xi\rfloor \end{aligned} $$

后面可以数论分块预处理$g(x)$ 然后再数论分块求答案

$\color{green}{代码}$

// CREATED BY MASHIROYUKI

#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#pragma GCC optimize("O3")
#define rep(i, x, n) for(int i = x; i <= n; i ++ )
#define downrep(i, x, n) for(int i = n; i >= x; i -- )

template<typename T> void debug(T x) {cout << "#debug: " << x << endl;}
template<typename T> void debug(T x, T y) {cout << "#debug: " << x << " " << y << endl;}
template<typename T>
void read(T &x){
    x = 0;
    char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
}
typedef long long ll;
typedef double db;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;

ll pr[N],mu[N],g[N];
bool vis[N];
ll n,m;

void pre()
{
    int n=5e4,tot=0;
    mu[1]=1;
    rep(i,2,n) {
        if(!vis[i]) pr[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&(ll)i*pr[j]<=n;j++) {
            vis[i*pr[j]]=true;
            if(!(i%pr[j])) break;
            mu[i*pr[j]]=-mu[i];
        }
    }
    rep(i,1,n) mu[i]+=mu[i-1];
    rep(x,1,n) {
        int t=0;
        for(int l=1,r,v;l<=x;l=r+1) {
            r=(v=x/l)?min(x/v,x):x;
            t+=(r-l+1)*v;
        }
        g[x]=t;
    }
}

void solve()
{
    read(n),read(m);
    if(n>m)swap(n,m);
    ll l,r,v1,v2,res=0;
    for(l=1;l<=n;l=r+1) {
        v1=n/l,v2=m/l;
        r=(v1&&v2)?min(n,min(n/v1,m/v2)):n;
        res+=(mu[r]-mu[l-1])*g[v1]*g[v2];
    }
    printf("%lld\n",res);
}

signed main()
{
    //IO
    pre();
    int t; read(t);
    while(t--) solve();
    return 0;
}