#include <bits/stdc++.h>

#define N 10000007

#define ll long long

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

int cnt;

int vis[N],prime[N],g[N],mu[N],nump[N],minp[N],qp[N];

void Initialize()

{

    int i,j;

    mu[1]=1;

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

    {

        if(!vis[i])

        {

            prime[++cnt]=i;

            nump[i]=1;

            minp[i]=i;

            qp[i]=i;

            g[i]=1;

        }

        for(j=1;j<=cnt&&prime[j]*i<N;++j)

        {

            vis[i*prime[j]]=1;

            int k=i*prime[j];

            if(i%prime[j])

            {

                nump[k]=1;

                qp[k]=minp[k]=prime[j];

                if(nump[i]==1) g[k]=-g[i];

            }

            else

            {

                nump[k]=nump[i]+1;

                minp[k]=prime[j];

                qp[k]=qp[i]*prime[j];

                if(k==qp[k])  g[k]=1;

                else if(nump[k]==nump[k/qp[k]]) g[k]=-g[k/qp[k]];

                break;

            }

        }

    }

    for(i=2;i<N;++i)  g[i]+=g[i-1];

}

void solve(int a,int b)

{

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

    int i,j;

    ll ans=0ll;

    for(i=1;i<=a;i=j+1)

    {

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

        ans=ans+(ll)(a/i)*(b/i)*(g[j]-g[i-1]);

    }

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

}

int main()

{

    // setIO("input");

    Initialize();

    int i,j,T;

    scanf("%d",&T);

    while(T--)

    {

        int a,b;

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

        solve(a,b);

    }

    return 0;

}