#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#include <vector>

const double eps=1e-8;
const ll inf=1e9;
const ll mod=1e9+7;
const int maxn=1e6+10;

int maxv=1e6;

bool vis[maxn];
int zhi[maxn],cnt_zhi,mu[maxn];
vector<int> vec[maxn];

int main()
{
    int t,n,m,i,j,k,p,q;
    ll sum,ans;
    for (i=2;i<=maxv;i++)
    {
        if (!vis[i])
        {
            zhi[++cnt_zhi]=i;
            mu[i]=-1;
        }
        for (j=1;j<=cnt_zhi;j++)
        {
            k=i*zhi[j];
            if (k>maxv)
                break;
            vis[k]=1;
            if (i%zhi[j]==0)
                break;
            else
                mu[k]=-mu[i];
        }
    }
    mu[1]=1;

    for (i=1;i<=maxv;i++)
    {
        sum=0;
        vec[i].push_back(0);
        for (j=i,k=1;j<=maxv;j+=i,k++)
        {
            sum+=mu[j];
            vec[i].push_back(sum);
        }
    }
//    exit(0);    ///2.147 s
//    printf("%d %d %d",vec[1][5],vec[1][3],vec[2][3]);

//    for (i=1;i<=5;i++)
//        printf("%d ",mu[i]);
//    printf("\n");
//    for (i=1;i<=5;i++)
//        printf("%d ",vec[1][i]);
//    printf("\n");
//    for (i=1;i<=5;i++)
//        printf("%d ",vec[2][i]);
//    printf("\n");

    scanf("%d",&t);
    while (t--)
    {
        sum=0;
        scanf("%d%d",&n,&m);
        p=min(n,m);
        ///array cal mu[i]!=0
        for (i=1;i<=p;i++)
            if (mu[i]!=0)
            {
                ans=0;
                q=p/i;
                for (j=1;j<=q;j++)
//                    ans+=1ll*mu[j]*vec[j][n/(i*j)]*vec[j][m/(i*j)];
                    ans+=1ll*mu[j]*vec[i*j][n/(i*j)]*vec[i*j][m/(i*j)];
                sum+=mu[i]*ans;
            }
        printf("%I64d\n",sum);
    }
    return 0;
}