#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int flg[maxn],pri[maxn],cnt=0;
int sum[maxn];
int S[maxn],C[maxn],V[maxn];
int pre[maxn],nxt[maxn];
int cur[maxn];
void init()
{
    S[1]=1,C[1]=0,V[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!flg[i]) pri[++cnt]=i,S[i]=i,C[i]=1,V[i]=i;
        for(int j=1;j<=cnt&&i*pri[j]<maxn;j++)
        {
            flg[i*pri[j]]=1;
            V[i*pri[j]]=pri[j];
            C[i*pri[j]]=C[i];
            S[i*pri[j]]=S[i];
            if(i%pri[j]==0) break;
            C[i*pri[j]]=C[i]+1;
            S[i*pri[j]]=S[i]*S[pri[j]];
        }
    }
    for(int i=1;i<=cnt;i++)
    for(long long j=pri[i];j<maxn;j*=pri[i])sum[j]=1;
    for(int i=maxn;i>1;i--)
    {
        vector<int>vec(1,1);
        int x=S[i];
        while(x>1)
        {
            int p=V[x];
            int lim=vec.size();
            for(int j=0;j<lim;j++)vec.push_back(vec[j]*p);
            x/=p;
        }
        nxt[i]=maxn;
        for(auto x:vec)nxt[i]=min(nxt[i],cur[x]==0?maxn:cur[x]);
        cur[S[i]]=i;   
    }
    memset(cur,0,sizeof(cur));
    for(int i=1;i<maxn;i++)
    {
        vector<int>vec(1,1);
        int x=S[i];
        while(x>1)
        {
            int p=V[x];
            int lim=vec.size();
            for(int j=0;j<lim;j++)vec.push_back(vec[j]*p);
            x/=p;
        }
        pre[i]=0;
        for(auto x:vec)pre[i]=max(pre[i],cur[x]);
        cur[S[i]]=i;
    }
}
int fa[maxn];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
struct edge
{
    int u,v,w;
    bool operator <(const edge &a)const
    {
        return w<a.w;
    }
}e[maxn*3];
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    init();
    //cout<<"ok"<<endl;
    cin.tie(0);
    ios::sync_with_stdio(0);
    int T;
    cin>>T;
    while(T--)
    {
        int l,r,ecnt=0;
        cin>>l>>r;
        int flag=0,pos=0;
        for(int i=l;i<=r;i++)if(sum[i])flag=1,pos=i;
        if(flag)
        {
            for(int i=l;i<=r;i++)e[++ecnt]={i,pos,S[i]%S[pos]==0?C[i]:C[i]+1};
            for(int i=l;i<=r;i++)
            {
               // cout<<pre[i]<<' '<<nxt[i]<<endl;
                if(pre[i]>=l)e[++ecnt]={i,pre[i],C[i]};
                if(nxt[i]<=r)e[++ecnt]={i,nxt[i],C[i]};
            }
        }
        else 
        {
            for(int i=l;i<=r;i++)
            for(int j=i+1;j<=r;j++)
            e[++ecnt]={i,j,S[i]+S[j]-S[gcd(i,j)]};
        }
        sort(e+1,e+ecnt+1);
        for(int i=l;i<=r;i++)fa[i]=i;
        int ans=0;
        for(int i=1;i<=ecnt;i++)
        {
            int fu=find(e[i].u),fv=find(e[i].v);
            if(fu!=fv)
            {
                fa[fu]=fv;
                ans+=e[i].w;
            }
        }
        cout<<ans<<'\n';
    }
}