#pragma GCC optimize(2)

 #pragma G++ optimzie(2)

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #define mod 100000009

 #define N 10000007

 #define ll long long

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int T,n,m;

 int tot;

 bool flag[N];

 ll h[N],pri[N];

 void init()

 {

     h[]=;

     for (int i=;i<N;i++)

     {

         if(!flag[i])

         {

             pri[++tot]=i;

             h[i]=(i-(ll)i*i)%mod;

         }

         for (int j=;j<=tot&&pri[j]*i<N;j++)

         {

             flag[pri[j]*i]=true;

             if(i%pri[j]==)

             {

                 h[pri[j]*i]=(pri[j]*h[i])%mod;

                 break;

             }

             else h[pri[j]*i]=(h[pri[j]]*h[i])%mod;

         }

     }

     for (int i=;i<N;i++)

         (h[i]+=h[i-])%=mod;

 }

 inline ll sum(ll x,ll y)

 {

     x%=mod,y%=mod;

     x*=(x+),(x=x/)%=mod;

     y*=(y+),(y=y/)%=mod;

     return x*y%mod;

 }

 ll query(int n,int m)

 {

     ll res=;

     if(n>m)swap(n,m);

     for (int i=,last;i<=n;i=last+)

     {

         last=min(n/(n/i),m/(m/i));

         res+=sum(n/i,m/i)*(h[last]-h[i-])%mod;

         res%=mod;

     }

     return (res%mod+mod)%mod;

 }

 int main()

 {

     T=read(),init();

     while(T--)

     {

         n=read(),m=read();

         printf("%lld\n",query(n,m));

     }

 }