#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;
typedef pair<int,int> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}

struct dsu{

    int n;
    int cc;
    vector<int>p,sz;
    vector<vector<int>>a;

    dsu(int n){
        this->n=n;
        this->cc=n;
        p.resize(n+1);
        sz.resize(n+1);
        a.resize(n+1);
        for(int i=1;i<=n;i++){
            p[i]=i;
            sz[i]=1;
            a[i].pb(i);
        }
    }

    void reset(){
        for(int i=1;i<=n;i++){
            p[i]=i;
            sz[i]=1;
            a[i].clear();
            a[i].pb(i);
        }
        cc=n;
    }
    int root(int x){
        if(p[x]==x)return x;
        return p[x]=root(p[x]);
    }
    bool join(int u,int v){
        u=root(u);
        v=root(v);
        if(u==v)return false;
        if(sz[u]>sz[v])swap(u,v);
        p[u]=v;
        sz[v]+=sz[u];
        for(int i=0;i<a[u].size();i++)a[v].pb(a[u][i]);
        a[u].clear();
        cc--;
        return true;
    }

};

const int maxn=1e6+10;
vector<int>divs[maxn];
int pos[maxn];

void prek(){

    for(int i=2;i<maxn;i++){
        if(pos[i])continue;
        for(int j=i;j<maxn;j+=i){
            pos[j]=1;
            divs[j].pb(i);
        }
    }
}

pair<int,int> niz[maxn];
void reset_structure(int r){
    for(int i=1;i<=r;i++)niz[i]={1e9,-1};
}
void dodaj_elem(int x){

    for(int i=0;i<(1<<divs[x].size());i++){
        int pom=1;
        for(int j=0;j<divs[x].size();j++)
            if(i&(1<<j))pom*=divs[x][j];

        niz[pom]=min(niz[pom],{divs[x].size()-__builtin_popcount(i),x});
    }

}
void dodaj_comp(int x,dsu &d,int l){

    for(int i=0;i<d.a[x].size();i++){
        int v=d.a[x][i];
        dodaj_elem(v+l-1);
    }

}
pair<int,pii> get_edge(int x,int l){

    int tn=x;
    x+=l-1;
    pii ret={1e9,-1};
    for(int i=0;i<(1<<divs[x].size());i++){
        int pom=1;
        for(int j=0;j<divs[x].size();j++)
            if(i&(1<<j))pom*=divs[x][j];

        ret=min(ret,niz[pom]);
        ///printf("%d %d %d OPA\n",pom,niz[pom].ff,niz[pom].ss);
    }
    ///printf("%d %d %d AAA\n",x,ret.ss,ret.ff);
    return {ret.ff+divs[x].size(),{ret.ss-l+1,tn}};
}
ll go(int l,int r){

    ll ret=0;
    int n=r-l+1;
    dsu d(n);
    while(d.cc>1){

        vector<int>cand;
        for(int i=1;i<=n;i++)pos[i]=0;
        for(int i=1;i<=n;i++){
            int x=d.root(i);
            if(pos[x])continue;
            cand.pb(x);
            pos[x]=1;
        }

        vector<pair<int,pii>>edges;
        const int inf=1e9;
        vector<pair<int,pii>> bestEdge(cand.size(),{inf,{0,0}});
        reset_structure(r);
        for(int i=0;i<cand.size();i++){
            int x=cand[i];

            pair<int,pii>pom={1e9,{-1,-1}};
            for(int j=0;j<d.a[x].size();j++){
                int c=d.a[x][j];
                pom=min(pom,get_edge(c,l));
               // printf("%d %d | %d\n",c+l-1,pom.ss.ff,pom.ff);
            }
            if(pom.ff>=1e9){}
            else bestEdge[i]=min(bestEdge[i],pom);
            dodaj_comp(cand[i],d,l);
        }

        reset_structure(r);
        reverse(cand.begin(),cand.end());
        for(int i=0;i<cand.size();i++){
            int x=cand[i];

            pair<int,pii>pom={1e9,{-1,-1}};
            for(int j=0;j<d.a[x].size();j++){
                int c=d.a[x][j];
                pom=min(pom,get_edge(c,l));
            }
            if(pom.ff>=1e9){}
            else bestEdge[i]=min(bestEdge[i],pom);
            if(bestEdge[i].first!=inf)edges.pb(bestEdge[i]);
            dodaj_comp(cand[i],d,l);
        }

        sort(edges.begin(),edges.end());
        for(int i=0;i<edges.size();i++){
            int w=edges[i].ff;
            int u=edges[i].ss.ff;
            int v=edges[i].ss.ss;
            if(d.root(u)==d.root(v))continue;
            ///printf("%d %d %d AA\n",u,v,w);
            ret+=w;
            d.join(u,v);
        }
       /// break;

    }

    return ret;
}

int main(){


    ///freopen("test.txt","r",stdin);

    prek();

    int t;
    scanf("%d",&t);
    while(t--){
        int l,r;
        scanf("%d %d",&l,&r);
        printf("%lld\n",go(l,r));
    }

    return 0;
}