#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<iostream>
#include<string>
#include<cmath>
#define N 10000010
#define M 100100
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
#define mmt(a,b) memset(a,b,sizeof(a))
typedef long long LL;
using namespace std;
int prime[10*M],A[M],B[M],c[M],mu[N],la,lb,len=0;
LL gs[N],g[N];bool b[N];
void init(int n)
{
  int i,j;mmt(b,0);mu[1]=1;g[1]=0;
  FOR(i,2,n)
  {
    if (!b[i]) {prime[++len]=i;mu[i]=-1;g[i]=1;}
    FOR(j,1,len)
    {     
      if (i*prime[j]>N) break;
      b[i*prime[j]]=1;
      if (i%prime[j]==0) {g[i*prime[j]]=mu[i];mu[i*prime[j]]=0;break;}
      else {g[i*prime[j]]=mu[i]-g[i];mu[i*prime[j]]=-mu[i];}
    }
  }
  gs[0]=0;
  FOR(i,1,n+1) gs[i]=gs[i-1]+g[i];
}
void DIV(int x,int *a,int &Len)
{
  int i,t=(int)sqrt(x);Len=0;
  FOR(i,2,t) a[++Len]=x/i+1;
  if (t*t!=x) a[++Len]=t+1;
  ROF(i,t,1) a[++Len]=i;
  FOR(i,1,Len/2) {int t=a[i];a[i]=a[Len-i+1];a[Len-i+1]=t;}
}
int main()
{
  //freopen("b2820.in","r",stdin);
  //freopen("b2820.out","w",stdout);
  init(1e7);int T,n,m;
  scanf("%d",&T);
  while (T--)
  {
    scanf("%d%d",&n,&m);
    DIV(n,A,la);DIV(m,B,lb);
    int i,j,p1=1,p2=1,Len=0;
    while (1)
    {
      if (A[p1]<B[p2]) c[++Len]=A[p1],p1++;
      if (A[p1]>B[p2]) c[++Len]=B[p2],p2++;
      if (A[p1]==B[p2]) c[++Len]=A[p1],p1++,p2++;
      if (p1>la||p2>lb) break;
    }
    FOR(i,p1,la) c[++Len]=A[i];FOR(i,p2,lb) c[++Len]=B[i];
    LL ans=0;
    c[Len+1]=max(n,m)+1;
    FOR(i,1,Len) 
     //if (c[i]<=min(n,m)) 
     ans+=(LL)(n/c[i])*(LL)(m/c[i])*(LL)(gs[min(c[i+1]-1,min(n,m))]-gs[c[i]-1]);
     //else break;
    printf("%lld\n",ans);
  }
}