假设$n\leq m$，并设$S_2(n)=\dfrac{n(n+1)}2$

$\begin{align*}\sum\limits_{i=1}^n\sum\limits_{j=1}^m[i,j]&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\dfrac{ij}{(i,j)}\\&=\sum\limits_{d=1}^nd\sum\limits_{i=1}^{\left\lfloor\frac nd\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac md\right\rfloor}ij[(i,j)=1]\\&=\sum\limits_{d=1}^nd\sum\limits_{e=1}^{\left\lfloor\frac nd\right\rfloor}\mu(e)e^2S_2\left(\left\lfloor\dfrac n{de}\right\rfloor\right)S_2\left(\left\lfloor\dfrac m{de}\right\rfloor\right)\end{align*}$

令$T=de$，答案为$\sum\limits_{T=1}^nS_2\left(\left\lfloor\dfrac nT\right\rfloor\right)S_2\left(\left\lfloor\dfrac mT\right\rfloor\right)T\sum\limits_{e|T}e\mu(e)$

$f(n)=n\sum\limits_{e|n}e\mu(e)$是积性函数，线性筛出前缀和即可

#include
     
      typedef long long ll;const int mod=100000009,T=10000000;int mul(int a,int b){return a*(ll)b%mod;}int ad(int a,int b){return(a+b)%mod;}void swap(int&a,int&b){a^=b^=a^=b;}int min(int a,int b){return a
      
       m)swap(n,m);	int i,nex,s;	s=0;	for(i=1;i<=n;i=nex+1){		nex=min(n/(n/i),m/(m/i));		s=ad(s,mul(f[nex]-f[i-1],mul(s2(n/i),s2(m/i))));	}	return ad(s,mod);}int main(){	sieve();	int t,n,m;	scanf("%d",&t);	while(t--){		scanf("%d%d",&n,&m);		printf("%d\n",solve(n,m));	}}