/**************************************************************

     Problem: 2693

     User: Tunix

     Language: C++

     Result: Accepted

     Time:5128 ms

     Memory:245416 kb

 ****************************************************************/

 //BZOJ 2693

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}

     return v*=sign;

 }

 /*******************tamplate********************/

 typedef long long LL;

 const int N=1e7+,P=;

 LL prime[N];

 LL h[N],sum[N]={};

 bool check[N];

 void getmu(int n){

     h[]=;

     int tot=;

     for(int i=;i<n;++i){

         if (!check[i]){

             prime[tot++]=i;

             h[i]=(i-(LL)i*i)%P;

         }

         rep(j,tot){

             if (i*prime[j]>n) break;

             check[i*prime[j]]=;

             if (i%prime[j]) h[i*prime[j]]=h[prime[j]]*h[i]%P;

             else{

                 h[i*prime[j]]=(prime[j]*h[i])%P;

                 break;

             }

         }

     }

     F(i,,n-)

         sum[i]=(sum[i-]+h[i])%P;

 }

 inline LL Sum(LL n,LL m){

     LL re1=n*(n+)/%P,

        re2=m*(m+)/%P;

     return re1*re2%P;

 }

 int main(){

     getmu(N-);

     int T=getint();

     LL n,m;

     while(T--){

         n=getint(); m=getint();

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

         LL i,last,ans=;

         for(i=;i<=n;i=last+){

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

             ans=(ans+Sum(n/i,m/i)*(sum[last]-sum[i-])%P)%P;

         }

         printf("%lld\n",(ans+P)%P);

     }

     return ;

 }