#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6+;

const int mod = 1e9+;

int phi[N+],is[N+],a[N+],b[N+],c[N+],n,m,t;

signed main(){

    int i,j,k,x=,y=;

    for(i=;i<=N;i++)phi[i]=i;

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

      if(!is[i])for(j=i;j<=N;j+=i)

       is[j]=,phi[j]=phi[j]/i*(i-);

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

      x=(x+*i+)%mod;

      y=(y+*i*i)%mod;

      a[i]=((i*i%mod*i%mod-x*i%mod+y)%mod+mod)%mod;

    }

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

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

        a[j]=(a[j]+2ll*i*phi[j/i]%mod)%mod;

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

      b[i]=(b[i-]+a[i]*i%mod)%mod;

      c[i]=(c[i-]+a[i]*i%mod*i%mod)%mod;

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

    }

    scanf("%lld",&t);

    while(t--){

      scanf("%lld%lld",&n,&m);

      n++,m++;

      int x=min(n,m);

      printf("%lld\n",((n*m%mod*a[x]%mod-(n+m)*b[x]%mod+c[x])%mod+mod)%mod);

    }

    return ;

}