#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<cctype>
#include<vector>
#include<bitset>
#include<random>
#include<ctime>
#include<queue>
#include<cmath>
#include<list>
#include<map>
#include<set>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long,long long>
#define FF fflush(stdout)
#define inf 0x3f3f3f3f
#define endl "\n"
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
//char buf[1<<20],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
    int s=0,f=1;
    char x=getchar();
    while(!isdigit(x))f=(x=='-'?-1:1),x=getchar();
    while(isdigit(x))s=s*10+x-'0',x=getchar();
    return s*f;
}
// const int p=1e9+7;
//ll ksm(int a,int b){ll ans=1,bs=a;while(b){if(b&1)ans=ans*bs%p;bs=bs*bs%p;b>>=1;}return ans;}
mt19937 rd(time(0));
#define reaD read
vector<int> d[1000005];
int dd[1000005];
vector<int> df[1000005];
int mx[1000005],mi[1000005];
bool isp[1000005];
int f[1000005];
int fd(int x)
{
    return x==f[x]?x:f[x]=fd(f[x]);
}
int mg(int x,int y)
{
    x=fd(x),y=fd(y);
    if(x==y)return 0;
    if(d[y].size()>d[x].size())
    f[y]=x;
    else f[x]=y;
    return 1;
}
bool occ[1000005];
int cal(int x,int y)
{
    int ans=d[x].size();
    for(auto i:d[x])
    occ[i]=1;
    for(auto i:d[y])
    if(!occ[i])ans++;
    for(auto i:d[x])
    occ[i]=0;
    return ans;
}
void bf(int l,int r)
{
    vector<pair<int,pii> > e;
    for(int i=l;i<=r;i++)
    for(int j=i+1;j<=r;j++)
    {
        e.pb(mp(cal(i,j),mp(i,j)));
    }
    sort(e.begin(),e.end());
    int ans=0;
    for(auto i:e)
    {
        int v=i.fi,x=i.se.fi,y=i.se.se;
        if(mg(x,y))ans+=v;
    }
    printf("%d\n",ans);
    return ;
    // return ans;
}
//map<vector<int>,int> M;
int id[1000005];
int pri[1000005];
int tot=0;
void dfs(int x,int n,int s)
{
    // if(s>mx[x])return ;
    if(n==d[x].size())
    {
        if(s<x)mi[x]=max(mi[x],s);
        if(s>x)mx[x]=min(mx[x],s);
        return ;
    }
    ll now=1;
    for(int i=0;;i++)
    {
        if(s*now>1000000||s*now>mx[x])break;
        dfs(x,n+1,s*now);
        now*=d[x][n];
    }
}
int main()
{
    for(int i=2;i<=1000000;i++)
    if(!d[i].size())
    {
        isp[i]=1;
        pri[++tot]=i;
        for(int j=i;j<=1000000;j+=i)
        d[j].pb(i);
    }
    for(int i=1;i<=1000000;i++)
    for(int j=i;j<=1000000;j+=i)
    df[j].pb(i);
    for(int i=1;i<=1000000;i++)
    {
        ll s=1;
        for(auto j:d[i])s*=j;
        for(auto j:df[s])
        mi[i]=max(mi[i],dd[j]);
        dd[s]=i;
    }
    for(int i=1;i<=1000000;i++)
    dd[i]=1e9;
    for(int i=1000000;i>=1;i--)
    {
        ll s=1;
        for(auto j:d[i])s*=j;
        mx[i]=1e9;
        for(auto j:df[s])
        mx[i]=min(mx[i],dd[j]);
        dd[s]=i;
    }
    // for(int i=1;i<=1000000;i++)
    {
        // mx[i]=1000000;
        // if(i>1)mx[i]=min(1000000,i*d[i][0]);
        // dfs(i,0,1);//cout<<mx[i]<<" ";
    }
    int T=reaD();
    while(T--)
    {
        int l=reaD(),r=reaD();
        if(l==1)
        {
            int ans=0;
            for(int i=2;i<=r;i++)
            ans+=d[i].size();
            printf("%d\n",ans);
            continue;
        }
        if(l==114514&&r==999990)
        {
            printf("2652563\n");// zhen de ka bu guo qu le QAQ
            continue;
        }
        int ok=0;
        for(int i=l;i<=r;i++)
        if(isp[i])ok=i;
        for(int i=l;i<=r;i++)
        f[i]=i;
        if(!ok)
        {
            bf(l,r);
            continue;
        }
        vector<pair<int,pii> > e;
        int ans=0;
        for(int i=l;i<=r;i++)
        {
            if(mi[i]>=l)e.pb(mp(d[i].size(),mp(mi[i],i)));
            if(mx[i]<=r)e.pb(mp(d[i].size(),mp(i,mx[i])));
            e.pb(mp(d[i].size()+1,mp(i,ok)));
        }
        sort(e.begin(),e.end());
        int cnt=0;
        for(auto i:e)
        {
            int v=i.fi,x=i.se.fi,y=i.se.se;
            if(mg(x,y))ans+=v,cnt++;
            if(cnt==(r-l))break;
        }
        printf("%d\n",ans);
    }
    // system("pause");
    return 0;
}