#include<bits/stdc++.h>
using namespace std;

#define Inf ll(1e18)
#define INF int(1e9)
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=1000005;
int test,n[15],m[15],cnt;
bool no[maxn];
int pri[maxn],mu[maxn],val[maxn],idn[15],idm[15];
int sumn[15][maxn],summ[15][maxn];
vector<int>fac[maxn];
vector<pii>ns,ms;
ll ans;

int main(){
    no[1]=true;mu[1]=1;
    for(int i=2;i<=1000000;i++){
        if(!no[i])pri[++cnt]=i,mu[i]=-1;
        REP(j,cnt){
            if(i*pri[j]>1000000)break;
            no[i*pri[j]]=true;
            if(i%pri[j]==0){
                mu[i*pri[j]]=0;
                break;
            }
            mu[i*pri[j]]=-mu[i];
        }
    }
    REP(i,1000000)if(mu[i])for(int j=i;j<=1000000;j+=i)if(mu[j])fac[j].pb(i);
    REP(i,1000000)if(mu[i]){
        rep(j,int(fac[i].size()))val[i]+=mu[fac[i][j]]*mu[i/fac[i][j]];
    }
    scanf("%d",&test);
    REP(t,test){
        scanf("%d%d",&n[t],&m[t]);
        ns.pb(mp(n[t],t));
        ms.pb(mp(m[t],t));
    }
    sort(ns.begin(),ns.end());
    rep(i,int(ns.size()))idn[ns[i].snd]=i+1;
    rep(i,int(ns.size())){
        REP(j,1000000)sumn[i+1][j]=sumn[i][j];
        for(int j=(!i?0:ns[i-1].fst)+1;j<=ns[i].fst;j++)if(mu[j]){
            rep(k,int(fac[j].size()))sumn[i+1][fac[j][k]]+=mu[j];
        }
    }
    sort(ms.begin(),ms.end());
    rep(i,int(ms.size()))idm[ms[i].snd]=i+1;
    rep(i,int(ms.size())){
        REP(j,1000000)summ[i+1][j]=summ[i][j];
        for(int j=(!i?0:ms[i-1].fst)+1;j<=ms[i].fst;j++)if(mu[j]){
            rep(k,int(fac[j].size()))summ[i+1][fac[j][k]]+=mu[j];
        }
    }
    REP(t,test){
        ans=0;
        REP(i,min(n[t],m[t]))if(mu[i])ans+=1LL*val[i]*sumn[idn[t]][i]*summ[idm[t]][i];
        printf("%I64d\n",ans);
    }
    return 0;
}