/*
 * Author: Endline
 * Time: 2024/02/04 20:58:43
 * File: Math-D.cpp
 */
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
using ll=long long;
const int MAXN=1000002;
const int mod=998244353;
template<typename _Tp>inline void Add(_Tp&x,ll y){x=x+y>=mod?x+y-mod:x+y;}
template<typename _Tp>inline void Mul(_Tp&x,ll y){x=x*y>=mod?x*y%mod:x*y;}
int T,l,r,pcnt,ecnt;
bool vis[MAXN],flg[MAXN];
int pri[MAXN],fa[MAXN],cnt[MAXN],val[MAXN],pre[MAXN],nxt[MAXN],mind[MAXN],las[MAXN];
vector<int>divor[MAXN];
struct edge
{
    int u,v,w;
}e[MAXN];
inline int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);}
inline void prework(int n)
{
    val[1]=1;
    for(int i=2;i<=n;i++)
    {
        val[i]=1;
        if(!vis[i])pri[++pcnt]=i;
        for(int j=1;j<=pcnt&&pri[j]*i<=n;j++)
        {
            vis[pri[j]*i]=true;
            if(i%pri[j]==0)break;
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j*i<=n;j++)
            divor[i*j].push_back(i);
    for(int i=1;i<=pcnt;i++)
        for(int j=1;pri[i]*j<=n;j++)
        {
            cnt[pri[i]*j]++,val[pri[i]*j]*=pri[i];
            if(!mind[pri[i]*j])mind[pri[i]*j]=pri[i];
        }
    for(int i=1;i<=n;i++)
        las[i]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j:divor[i])
            pre[i]=max(pre[i],las[j]);
        las[val[i]]=i;
    }
    for(int i=1;i<=n;i++)las[i]=n+1;
    for(int i=n;i>=1;i--)
    {
        nxt[i]=n+1;
        for(int j:divor[i])
            nxt[i]=min(nxt[i],las[j]);
        las[val[i]]=i;
    }
    return;
}
inline bitset<MAXN>calc(int x)
{
    bitset<MAXN>ans;
    for(int i=1;i<=pcnt&&pri[i]*pri[i]<=x;i++)
    {
        if(x%pri[i]==0)
        {
            ans.set(pri[i]);
            while(x%pri[i]==0)x/=pri[i];
        }
    }
    if(x>1)ans.set(x);
    return ans;
}
inline int Kruskal()
{
    int ans=0;
    sort(e+1,e+ecnt+1,[](edge x,edge y){return x.w<y.w;});
    for(int i=l;i<=r;i++)fa[i]=i;
    for(int i=1;i<=ecnt;i++)
    {
        if(getf(e[i].u)==getf(e[i].v))continue;
        fa[getf(e[i].u)]=getf(e[i].v);
        ans+=e[i].w;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    prework(1000000);
    cin>>T;
    while(T--)
    {
        cin>>l>>r;
        int pl=lower_bound(pri+1,pri+pcnt+1,l)-pri,pr=lower_bound(pri+1,pri+pcnt+1,r)-pri;
        if(pl==pr)
        {
            ecnt=0;
            for(int i=l;i<=r;i++)
                for(int j=i+1;j<=r;j++)
                    e[++ecnt]={i,j,(int)(calc(i)|calc(j)).count()};
        }
        else
        {
            ecnt=0;
            int pos=0;
            for(int i=l;i<=r;i++)if(!vis[i]&&!pos)pos=i;
            for(int i=l;i<=r;i++)
            {
                if(pre[i]>=l)e[++ecnt]={i,pre[i],cnt[i]};
                if(nxt[i]<=r)e[++ecnt]={i,nxt[i],cnt[i]};
                if(i!=pos)e[++ecnt]={i,pos,cnt[i]+1};
            }
        }
        printf("%d\n",Kruskal());
    }
    return 0;
}