#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long i64;
const int N = 1e7+10;

int pr[N], tot, mu[N];
i64 s[N];
bool flag[N], f[N];

void Init() {
    memset(f, 1, sizeof f);
    for (int i = 1; i*i < N; ++i) 
        f[i*i] = 0;
    mu[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (!flag[i]) {
            pr[++tot] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= tot; ++j) {
            int k = pr[j];
            if (i * k >= N) break;
            flag[i*k] = 1;
            if (i % k == 0) {
                mu[i*k] = 0;
                break;
            }
            else
                mu[i*k] = mu[i] * mu[k];
        }
    }
    for (int i = 1; i < N; ++i) if (mu[i])
        for (int j = 1; j*i < N; ++j)
            s[j*i] += mu[i] * f[j];
    for (int i = 1; i < N; ++i)
        s[i] += s[i-1];
}

int main() {

    Init();
    int tcase;
    scanf("%d", &tcase);
    while (tcase--) {
        int n, m;
        scanf("%d%d", &n, &m);
        if (n > m) swap(n, m);
        i64 ans = 0;
        for (int i = 1; i <= n; ++i) {
            int j = min(n / (n/i), m / (m/i));
            j = min(j, n);
            ans += 1ll * (n/i) * (m/i) * (s[j] - s[i-1]);
            i = j;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}