#include
#include
#include
#include
#include
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int read()
{
char q=getchar();int ans=0;
while(q<‘0‘||q>‘9‘)q=getchar();
while(q>=‘0‘&&q<=‘9‘){ans=ans*10+q-‘0‘;q=getchar();}
return ans;
}
const int mod=100000009;//多打了一个0
const int N=10000006;
int prime[N],cnt;
bool he[N];
int mu[N];
ll ji[N];
int T,n,m;
void chu()
{
mu[1]=1;ji[1]=1;
for(int i=2;ii)
{
if(!he[i])
{
prime[++cnt]=i;
mu[i]=-1;
ji[i]=(((ll)i-(ll)i*i)%mod+mod)%mod;
}
for(int j=1;j<=cnt&&prime[j]*ij)
{
he[i*prime[j]]=1;
if(i%prime[j]==0)
{
mu[i*prime[j]]=0;
ji[i*prime[j]]=ji[i]*prime[j]%mod;
// 有>2个prime[j]因子的mu是0,所以多出来的只有f[i]*prime[j]
break;
}
mu[i*prime[j]]=-mu[i];
ji[i*prime[j]]=ji[i]*ji[prime[j]]%mod;
}
}
for(int i=1;ii)
ji[i]=(ji[i]+ji[i-1])%mod;
}
ll sum(ll x,ll y)
{
ll t1,t2;
t1=(x+1)*x/2%mod;
t2=(y+1)*y/2%mod;
return t1*t2%mod;
}
ll work()
{
if(n>m)
swap(n,m);
ll ans=0;
int nx;
for(int i=1;i<=n;i=nx+1)
{
nx=min( n/(n/i),m/(m/i) );
ans=(ans+sum(n/i,m/i)*(ji[nx]-ji[i-1]+mod)%mod)%mod;
}
return (ans+mod)%mod;
}
int main(){
//freopen("in.in","r",stdin);
//freopen("bzoj_2693.in","r",stdin);
//freopen("bzoj_2693.out","w",stdout);
chu();
T=read();
while(T--)
{
n=read();m=read();
//printf("n=%d m=%d\n",n,m);
printf("%lld\n",work());
}
}