#include <bits/stdc++.h>
using namespace std;
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
#define int long long
#define Rep(x, a, b) for(int x = a; x <= b; ++ x)
#define Dep(x, a, b) for(int x = a; x >= b; -- x)
#define Next(i, x) for(int i = head[x]; i ; i = e[i].nxt)
int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
const int maxn = 1e7 + 10;
const int XRZ = 999911658;
int cnt, Mu[maxn], vis[maxn], Prime[maxn];
int oula(int n) {
    Mu[1] = 1;
    Rep(i, 2, n) {
        if(vis[i] == 0) Mu[i] = -1, Prime[++ cnt] = i;
        for(int j = 1; j <= cnt && i * Prime[j] <= n; ++ j) {
            vis[Prime[j] * i] = 1;
            if(i % Prime[j] == 0) break;
            Mu[Prime[j] * i] = -Mu[i];
        }
    }
} int F[maxn], sum[maxn];
signed main() {
    oula(maxn - 10);
    Rep(i, 1, cnt) for(int j = 1; j * Prime[i] <= maxn - 10; ++ j) F[j * Prime[i]] += Mu[j];
    Rep(i, 1, maxn - 10) sum[i] = sum[i - 1] + F[i];
    int T = read();
    while(T --) {
        int l = read(), r = read(), ans = 0;
        if(l > r) swap(l, r);
        for(int i = 1, j; i <= l; i = j + 1) {
            j = min(l / (l / i), r / (r / i));//取2个块下一个的最小值，整数分块。
            ans += (l / i) * (r / i) * (sum[j] - sum[i - 1]);
        } printf("%lld\n", ans);
    }
	return 0;
}

没开O2 90ps 开了O2 直接0ps /ll/kk/wq