#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define clr(x,y) memset(x,y,sizeof(x))
#define in(a) a=read()
#define out(a) printf("%d\n",a)
inline ll read(){
    char c=getchar();ll f=1,x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return x*f;
}
#define mod 998244353
void MOD(int &x){if(x>=mod)x-=mod;}
#define maxn 1000010
#define inf (1<<30)
int u[maxn],vis[maxn],mn[maxn],cnt[maxn];
int a1[maxn],b1[maxn],a2[maxn],b2[maxn];
ll aa[maxn],bb[maxn],ab[maxn],ba[maxn];
int main(){
    FOR(i,1,1000000)vis[i]=1;
    FOR(i,2,1000000)
        if(!u[i]){
            for(int j=i;j<=1000000;j+=i){
                u[j]=1;
                if(j%(i*i)==0)vis[j]=0;
                if(!mn[j])mn[j]=i;
            }
        }
    FOR(i,1,1000000)
        if(vis[i]){
            int c=i;
            while(c!=1){
                c/=mn[c];
                cnt[i]++;
            }
        }
    int t;
    in(t);
    while(t--){
        int n,m;
        in(n);in(m);
        if(n<m)swap(n,m);
        ll ans=0;
        clr(a1,0);clr(b1,0);clr(b2,0);clr(a2,0);
        FORD(i,m,1)if(vis[i]){
            for(int j=i;j<=n;j+=i)
                if(vis[j]){
                    if(cnt[j]%2==0)a1[i]++;
                    if(cnt[j]%2==1)b1[i]++;
                }
            for(int j=i;j<=m;j+=i)
                if(vis[j]){
                    if(cnt[j]%2==0)a2[i]++;
                    if(cnt[j]%2==1)b2[i]++;
                }
            aa[i]=1ll*a1[i]*a2[i];
            ab[i]=1ll*a1[i]*b2[i];
            ba[i]=1ll*b1[i]*a2[i];
            bb[i]=1ll*b1[i]*b2[i];
            for(int j=i+i;j<=m;j+=i){
                aa[i]-=aa[j];
                ab[i]-=ab[j];
                ba[i]-=ba[j];
                bb[i]-=bb[j];
            }
            if(cnt[i]%2==0){
                ans+=aa[i]+bb[i];
                ans-=ab[i]+ba[i];
            }
            else{
                ans-=aa[i]+bb[i];
                ans+=ab[i]+ba[i];
            }
        }
        printf("%lld\n",ans);
    }
}