#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<algorithm>
#define FILE "read"
using namespace std;
typedef long long ll;
const int MAXN=(int)1e7,D(50);
int cnt,check[MAXN+D],mu[MAXN+D],prime[1000000+D],sum[MAXN+D];
namespace INIT{
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
int x=0,f=1; char ch=getc();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();}
return x*f;
}
}using namespace INIT;
void pre(){
mu[1]=1;
for(int i=2;i<=MAXN;++i){
if(!check[i]) prime[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&prime[j]*i<=MAXN;++j){
check[prime[j]*i]=1;
if(i%prime[j]==0) {mu[i*prime[j]]=0; break;}
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=cnt;++i){
for(int j=1;j*prime[i]<=MAXN;++j)
sum[j*prime[i]]+=mu[j];
}
for(int i=1;i<=MAXN;++i) sum[i]+=sum[i-1];
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
int T=read(); pre();
while(T--){
int n=read(),m=read(),last;
ll ans=0;
if(n>m) swap(n,m);
for(int i=1;i<=n;i=last+1){
last=min(n/(n/i),m/(m/i));
ans+=(ll)(n/i)*(m/i)*(sum[last]-sum[i-1]);
}
printf("%lld\n",ans);
}
return 0;
}