#include<cstdio>

#include<queue>

#include<cctype>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=;

int miu[N],su[N],sum[N];

ll f[N];

bool he[N];

void Euler(int n){

    int tot=;

    miu[]=;

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

    if(!he[i]){

        su[++tot]=i;

        miu[i]=-;

    }

    for(int j=;j<=tot;j++){

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

        he[i*su[j]]=;

        if(i%su[j]==){

        miu[i*su[j]]=;break;

        }

        else miu[i*su[j]]=-miu[i];

    }

    }

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

    int p=su[i];

    for(int j=;j*p<=n;j++)f[j*p]+=miu[j];

    }

    for(int i=;i<=n;i++)f[i]+=f[i-];

    return;

}

int main(){

    Euler();

    int t;

    scanf("%d",&t);

    while(t--){

    int a,b;ll ans=;

    scanf("%d%d",&a,&b);

    if(a>b)swap(a,b);

    for(int i=,j;i<=a;i=j+){

        j=min(a/(a/i),b/(b/i));

        ans+=(f[j]-f[i-])*(a/i)*(b/i);

    }

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

    }

    return ;

}