#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;

}