#include<bits/stdc++.h>
using namespace std;
long long prim[10000001],cnt=0,mu[10000001];
bool vis[10000001];
void get_mu(long long n) {
	mu[1]=1;
	for(int i=2;i<=n;i++) {
		if(!vis[i])	cnt++,prim[cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&prim[j]*i<=n;j++) {
			vis[i*prim[j]]=1;
			if(!(i%prim[j])) {
				mu[i*prim[j]]=0;
				break;
			}
			mu[i*prim[j]]=-mu[i];
		}
	}
}
long long f[10000001];
long long x[10001],y[10001];
long long add[10000001];
void solve(long long n,long long m) {
	if(n>m)
		swap(n,m);
	long long ans=0,left=1,right=0;
	while(left<=n) {
		right=min(n/(n/left),m/(m/left));
		ans+=1ll*(add[right]-add[left-1])*(long long)(n/left)*(long long)(m/left);
		left=right+1;
	}
	printf("%lld\n",ans);
}
void get_sum(long long n) {
	for(int i=1;i<=cnt;i++) 
		for(int j=1;j*prim[i]<=n&&j<=cnt;j++) 
			f[prim[i]*j]+=mu[j];
}
void get_add(long long n) {
	for(int i=1;i<=n;i++)
		add[i]=add[i-1]+f[i];
}
long long t;
int main() { 
	scanf("%lld",&t);
	for(int i=1;i<=t;i++)
		scanf("%lld%lld",&x[i],&y[i]);
	get_mu(10000000);
	get_sum(10000000);
	get_add(10000000);
	for(int i=1;i<=t;i++)
		solve(x[i],y[i]);
}