#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-1);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
ld eps=1e-9;
ll pp=998244353;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll read(){
    ll ans=0;
    char last=' ',ch=getchar();
    while(ch<'0' || ch>'9')last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans;
    return ans;
}
//head
#define N 1100000
int prime[N],rec[N],u[N],num=0;
bool vis[N];
ll s[N][2][2];
int n,m;
void solved(){
    n=read(),m=read();
    if(n<m)swap(n,m);
    rep(i,1,m){
        rep(k1,0,1)
            rep(k2,0,1)
                s[i][k1][k2]=0;
        if(u[i]==0)continue;
        ll c1[2],c2[2];
        c1[0]=c1[1]=c2[0]=c2[1]=0;
        for(int j=i;j<=n;j+=i)
            if(u[j]==-1)c1[1]++;
            else
            if(u[j]==1)c1[0]++;

        for(int j=i;j<=m;j+=i)
            if(u[j]==-1)c2[1]++;
            else
            if(u[j]==1)c2[0]++;
        s[i][0][0]=c1[0]*c2[0];
        s[i][0][1]=c1[0]*c2[1];
        s[i][1][0]=c1[1]*c2[0];
        s[i][1][1]=c1[1]*c2[1];
    }
    ll ans0=0, ans1=0;
    for(int i=m;i>=1;i--)
        if(u[i]!=0){
            for(int j=i*2;j<=m;j+=i)
                rep(k1,0,1)
                    rep(k2,0,1)
                        s[i][k1][k2]-=s[j][k1][k2];
            int cnt;
            if(u[i]==1)cnt=0;
            else cnt=1;
            rep(k1,0,1)
                rep(k2,0,1){
                    //printf("%d %d %d : %d\n",i,k1,k2,(int)s[i][k1][k2]);
                    if((k1+k2+cnt)%2)ans1+=s[i][k1][k2];
                    else ans0+=s[i][k1][k2];
                }
        }
    cout<<ans0-ans1<<endl;
}
int main(){
    int nn=1000000;
    num=0;
    rep(i,2,nn){
        if(!vis[i]){
            prime[++num]=i;
            rec[i]=i;
        }
        for(int j=1;j<=num && prime[j]*i<=nn;j++){
            vis[prime[j]*i]=1;
            rec[prime[j]*i]=prime[j];
            if(i%prime[j]==0)break;
        }
    }
    u[1]=1;
    rep(i,2,nn){
        if((i/rec[i]) % rec[i]==0)u[i]=0;
        else u[i]=u[i/rec[i]]*(-1);
    }
    //rep(i,1,nn)cout<<i<<" "<<rec[i]<<endl;
    int T=read();
    while(T--)solved();
    return 0;
}