#include<bits/stdc++.h>

 #define  ll long long

 using namespace std;

 const int N = 1e7 + ;

 int t;

 //线性筛法求莫比乌斯函数

 bool vis[N + ];

 int pri[N + ];

 int mu[N + ];

 ll sum[N];

 int f[N];

 void mus() {

     memset(vis, , sizeof(vis));

     memset(f,, sizeof(f));//f[n]=sum(mu[n/p])

     mu[] = ;

     int tot = ;

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

         if (!vis[i]) {

             pri[tot++] = i;

             mu[i] = -;

         }

         for (int j = ; j < tot && i * pri[j] < N; j++) {

             vis[i * pri[j]] = ;

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

                 mu[i * pri[j]] = ;

                 break;

             }

             else  mu[i * pri[j]] = -mu[i];

         }

     }

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

         for(int j=;j<tot&&pri[j]*i<N;j++) f[i*pri[j]]+=mu[i];//需要重复更新，不能放在线性筛内部

     sum[]=;

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

 }

 int n,m,k;

 ll cal(int x,int y){

     int ma=min(x,y);

     ll res=;

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

         j=min(x/(x/i),y/(y/i));

         if(j>=ma) j=ma;

         res+=1ll*(sum[j]-sum[i-])*(x/i)*(y/i);

     }

     return res;

 }

 int main() {

     mus();

     scanf("%d",&t);

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

         scanf("%d%d",&n,&m);

         ll ans;

         ans=cal(n,m);

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

     }

     return ;

 }