#include<iostream>
#include<cstdio>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
#define bug cout<<"~~~~~~~~"<<'\n';
#define bugout(x) cout<<x<<endl;
using namespace std;
typedef long long lxl;
template<typename T>
inline T  max(T &a, T &b) {
	return a > b ? a : b;
}
template<typename T>
inline T  min(T &a, T &b) {
	return a < b ? a : b;
}

inline char gt() {
	static char buf[1 << 21], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void  read(T &x) {
	register char ch = gt();
	x = 0;
	int w(0);
	while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
	while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
	w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x) {
	if(x < 0) x = -x, putchar('-');
	char ch[20];
	int num(0);
	while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
	while(num) putchar(ch[num--]);
	putchar('\n');
}

const int N = 1e7 + 79;
int T, n, m;
#define int long long
int v[N+55],prime[N+55],mu[N+55],cnt;
lxl f[N+55],ans;

inline void getmu(){
	mu[1]=1;
	rep(i,2,N){
		if(!v[i]){
			v[i]=i;
			prime[++cnt]=i;
			mu[i]=-1;
		}
		rep(j,1,cnt){
			if(prime[j]>v[i]||1ll*prime[j]*i>N) break;
			v[i*prime[j]]=i;
			if(i%prime[j]==0){
				mu[i*prime[j]]=0;
				break;
			}
			else mu[i*prime[j]]=-mu[i];
		}
	}
	rep(i,1,cnt){
       for(register int j(1);1ll*j*prime[i]<=N;++j) f[j*prime[i]]+=mu[j];		
	}
	rep(i,1,N-1) f[i]+=f[i-1];
}

 main() {
	read(T);
	getmu();
	
	while(T--) {
		ans=0;
		read(n);
		read(m);
		
		if(n>m) swap(n,m);
		
		for(register int i=1,j;i<=n;i=j+1){
			j=min(n/(n/i),m/(n/i));
			ans+=(f[j]-f[i-1])*(n/i)*(m/i);//ǰ׺ºÍ 
		}
		out(ans);	
	}
	return 0;
}

求助