#include <bits/stdc++.h>
using namespace std;
#define int long long
#define open(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

/*这里是fread+fwrite的IO优化，定义了int read(void)、void write(void)和void putc(char)*/

const int maxn = 1e7 + 700;
bool isnot[maxn] = {true, true};
signed pri[700000], tot = 0, func[maxn];
inline signed mymin(signed a, signed b) {return a < b? a: b;}

signed main() {
//	open("临时文件4v8Lw0ixwFeNIwJ5BMjErhr6hStYZ7HfniylAtLDYHsP1iuLAajAkR4U15o0kmmmwTOxjDib3O57NVrorzJfvDdWiMVrTo1dufKnDkSUAYL8ueFrv9Gq9LoRM3elYangd0oVukAvq7dSpF6ObFzQ6");
	
	{
		int mid = 0;
		for(int i = 2; i <= 10000000; i++) {
			if(not isnot[i]) {
				tot++, pri[tot] = i;
				func[i] = 1;
			}
			for(int j = 1; j <= tot and i * pri[j] <= 10000000; j++) {
				mid = i * pri[j];
				isnot[mid] = true;
				if(i % pri[j]) {
					if(func[i] == 0) func[mid] = 0;
					else if(isnot[i]) func[mid] = (func[i] == 1 or func[i] == -1? -func[i]: -func[i] + (func[i] < 0? 1: -1));
					else func[mid] = -2;
				} else {
					if(func[i] == 0) func[mid] = 0;
					else if(isnot[i]) func[mid] = (func[i] == 1 or func[i] == -1? 0: (func[i] < 0? 1: -1));
					else func[mid] = -1;
					break;
				}
			}
		}
	}
	
	for(int i = 2; i <= 10000000; i++) func[i] += func[i - 1];
	
	int TIM = read();
	while(TIM--) {
		signed n = read(), m = read(); int ans = 0;
		if(n < m) swap(n, m);
		for(int i = 2, j = 0; i <= m; i = j + 1) {
			j = mymin(n / (n / i), m / (m / i));
			ans += 1ll * (n / i) * (m / i) * (func[j] - func[i - 1]);
		}
		write(ans), putc('\n');
	}
	
	return 0;
}

80过不去……