#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <cmath>

using namespace std;

typedef long long ll;

const int maxn = 1e5+;

int t;

int x, y;

int len;

int pnum;

int p[maxn];

bool e[maxn];

ll res, ans;

vector<int> g[maxn];

void prime() {

    e[] = e[] = ; pnum = ;

    for(int i = ; i < maxn; i++) {

        if(e[i]==) p[++pnum] = i;

        for(int j = ; j<=pnum && p[j]*i<maxn; j++) {

            e[p[j]*i] = ;

            if(i%p[j]==) break;

        }

    }

}

int gcd(int x, int y) {

    return y==?x:gcd(y, x%y);

}

int lcm(int x, int y) {

    return x/gcd(x, y)*y;

}

void dfs(int cur, int tol, int sum, int id) {

    if(cur >= len) return ;

    int p = lcm(g[id][cur], sum);

    if(tol&) res -= y/p;

    else res += y/p;

    dfs(cur+, tol+, p, id);

    dfs(cur+, tol, sum, id);

}

int main() {

    prime();

    for(int i = ; i <= pnum; i++) {

        int cnt = ;

        while(cnt*p[i] <= ) {

            g[cnt*p[i]].push_back(p[i]);

            cnt++;

        }

    }

    scanf("%d", &t);

    while(t--) {

        scanf("%d%d", &x, &y);

        if(x > y) swap(x, y);

        ans = y;

        for(int i = ; i <= x; i++) {

            res = ;

            len = g[i].size();

            dfs(, , , i);

            ans += y-res;

        }

        printf("%lld\n", ans);

    }

}