#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;

int p[N],top,v[N],w[N],s[N],g[N];

void primes(int n=N-1){
    g[1]=1;
    for(int i=2;i<=n;i++){
        s[i]=s[i-1];
        if(!v[i])v[i]=p[++top]=i,s[i]++,w[i]=1,g[i]=i;
        for(int j=1;j<=top;j++){
            if(p[j]>v[i]||p[j]>n/i)break;
            v[i*p[j]]=p[j];
            if(i%p[j]==0)w[i*p[j]]=w[i],g[i*p[j]]=g[i];
            else w[i*p[j]]=w[i]+1,g[i*p[j]]=g[i]*p[j];
        }
    }
}

int calc(int x,int y){
    return w[x]+w[y]-w[__gcd(x,y)];
}

bool vis[N];
int dis[N],b[N];
int prim(int l,int r){
    int ret=0;
    for(int i=l;i<=r;i++)vis[i]=0;
    vis[l]=1;
    for(int i=l;i<=r;i++)dis[i]=calc(l,i);
    for(int j=l;j<r;j++){
        int x=0,ans=0x3f3f3f3f;
        for(int i=l;i<=r;i++)
            if(!vis[i]&&dis[i]<ans)x=i,ans=dis[i];
        vis[x]=1,ret+=ans;
        for(int i=l;i<=r;i++)
            if(!vis[i])dis[i]=min(dis[i],calc(x,i));
    }
    return ret;
}

void solve(){
    int l,r,ans=0;
    scanf("%lld%lld",&l,&r);
    if(l==r){
        puts("0");
        return;
    }
    if(l==1){
        for(int i=2;i<=r;i++)ans+=w[i];
        printf("%lld\n",ans);
        return;
    }
    if(s[r]==s[l-1]){
        printf("%lld\n",calc(l,r));
        return;
    }
    for(int i=1;i<=r;i++)b[i]=0;
    for(int i=l;i<=r;i++)b[g[i]]++;
    for(int i=1;i<=r;i++){
        if(b[i])ans+=(b[i]-1)*w[i];
    }
    for(int i=1;i<=r;i++)
        if(b[i])
            for(int j=i*2;j<=r;j+=i)
                if(b[j])ans+=w[j],b[j]=0;
    for(int i=1;i<=r;i++)
        if(b[i])ans+=w[i]+1;
    printf("%lld\n",ans-2);
}

signed main(){
    primes();
    int T;scanf("%lld",&T);
    while(T--)solve();
    return 0;
}