#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=1e7+;

int vis[maxn];

int mu[maxn];

int prime[maxn];

int tot=;

int sum1[maxn];

int sum2[maxn];

void get_mu()

{

    mu[]=; vis[]=;

    for(int i=;i<maxn;i++)

    {

        if(!vis[i]) {mu[i]=-; prime[++tot]=i; }

        for(int j=;j<=tot && i*prime[j]<maxn;j++)

        {

            vis[i*prime[j]]=;

            if(i%prime[j]==) break;

            mu[i*prime[j]]=-mu[i];

        }

    }

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

        for(int j=prime[i];j<maxn;j+=prime[i])

            sum1[j]+=mu[j/prime[i]];

    for(int i=;i<=maxn;i++)

        sum2[i]=sum2[i-]+sum1[i];

}

int main()

{

    get_mu();

    int T; cin>>T;

    while(T--)

    {

        int n,m; cin>>n>>m;

        ll ans=;

        for(int l=,r;l<=min(n,m);l=r+)

        {

           // r=min(n,m)/(min(n,m)/l);  // l-r;

           r=min( n/(n/l),m/(m/l));

            ans+=1ll*(n/l)*(m/l)*(sum2[r]-sum2[l-]);

        }

        /*int t=0;

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

        {

            for(int j=1;j<=m;j++)

            {

                if(vis[__gcd(i,j)]==0) t++;

            }

        }*/

        cout<<ans<<endl;

    }

}