include<bits/stdc++.h>

using namespace std;
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k'-') f=-1;
while(isdigit(k)) res=res10+k-'0',k=getchar();
return resf;
}
const int N=1e7+10,mod=100000009;
#define ll long long
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
ll sum[N];
int pri[N],cnt,mu[N],fl[N];
inline void prework()
{
mu[1]=1; sum[1]=1;
for(int i=2;i<N;++i)
{
if(!fl[i]) sum[i]=(1-i+mod)%mod,pri[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&ipri[j]<N;++j)
{
fl[ipri[j]]=1;
if(i%pri[j]0){sum[pri[j]i]=sum[i]; break;}
else sum[pri[j]i]=1llsum[i]sum[pri[j]]%mod;
}
}
for(int i=1;i<N;++i) sum[i]=1llsum[i]i%mod;
for(int i=1;i<N;++i) sum[i]=add(sum[i],sum[i-1]);
return ;
}
inline int f(int x){return 1llx(x+1)/2%mod;}
inline void work()
{
int n=read(),m=read();
ll ans=0;
if(n>m) swap(n,m);
for(int l=1,r;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans=(ans+1llf(n/l)f(m/l)%mod*((sum[r]-sum[l-1]+mod)%mod)%mod)%mod;
} printf("%lld\n",ans);
return ;
}
signed main()
{
prework(); int T=read();
while(T--) work();
return 0;
}
}
signed main(){return yspm::main();}