#include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<string>

 #include<cstring>

 #define re(i,l,r) for(int i=(l);i<=(r);i++)

 #define rre(i,r,l) for(int i=(r);i>=(l);i--)

 using namespace std;

 typedef long long LL;

 int prime[],prime_tot,mu[],g[],sum[];

 bool bo[];

 LL solve(int n,int m)

 {

     LL ret=;

     if(n>m)swap(n,m);

     int i=,xia;

     while(i<=n)

     {

         xia=min(n/(n/i),m/(m/i));

         ret+=1LL*(n/i)*(m/i)*(sum[xia]-sum[i-]);

         i=xia+;

     }

     return ret;

 }

 int main()

 {

     mu[]=;

     re(i,,)

     {

         if(!bo[i])prime[++prime_tot]=i,mu[i]=-,g[i]=;

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

         {

             bo[i*prime[j]]=;

             if(i%prime[j]==){mu[i*prime[j]]=,g[i*prime[j]]=mu[i];break;}

             else mu[i*prime[j]]=-mu[i],g[i*prime[j]]=mu[i]-g[i];

         }

     }

     re(i,,)sum[i]=sum[i-]+g[i];

     int t;

     scanf("%d",&t);

     while(t--)

     {

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

         printf("%lld\n",solve(n,m));

     }

     return ;

 }