#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e7+10, MD=100000009;int p[N], pcnt, mx;bool np[N];ll g[N];void init() {	g[1]=1;	int i, j, t;	for(i=2; i<=mx; ++i) {		if(!np[i]) p[++pcnt]=i, g[i]=1-i;		for(j=1; j<=pcnt; ++j) {			t=p[j]*i; if(t>mx) break;			np[t]=1;			if(i%p[j]==0) { g[t]=g[i]; break; }			g[t]=g[i]*(1-p[j]);		}	}	for(i=2; i<=mx; ++i) g[i]*=i;	for(i=1; i<=mx; ++i) g[i]+=g[i-1], g[i]%=MD;}int nn[10005], mm[10005];int main() {	int t; scanf("%d", &t);	for(int i=1; i<=t; ++i) scanf("%d %d", &nn[i], &mm[i]), mx=max(max(nn[i], mm[i]), mx);	init();	for(int k=1; k<=t; ++k) {		int n=nn[k], m=mm[k]; if(n>m) swap(n, m);		ll ans=0, t1, t2;		for(int i=1, pos=0; i<=n; i=pos+1) {			pos=min(n/(n/i), m/(m/i));			t1=((ll)(n/i)*(n/i+1)/2)%MD;			t2=((ll)(m/i)*(m/i+1)/2)%MD;			ans+=((g[pos]-g[i-1])*((t1*t2)%MD))%MD;			ans%=MD;		}		printf("%lld\n", ((ans%MD)+MD)%MD);	}	return 0;}