#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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],mval[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);
            mval[j]*=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 preccc(dsu &d,int l,int r){

    ll ret=0;
    for(int i=1;i<=r;i++)pos[i]=0;
    int cpc=0;
    for(int i=l;i<=r;i++){
        if(pos[mval[i]]==0)pos[mval[i]]=i;
        else{
            ret+=divs[i].size();
            d.join(i-l+1,pos[mval[i]]-l+1);
            cpc++;
        }
    }
    for(int i=1;i<=r-l+1;i++)d.a[i].resize(1);
    //printf("%d cpc\n",cpc);
    return ret;
}
ll go(int l,int r){

    ll ret=0;
    int n=r-l+1;
    dsu d(n);
    ret=preccc(d,l,r);
    /*d.join(1,2);
    d.join(2,3);*/
    int ccc=0;
    while(d.cc>1){

        /*if(ccc==1){
            while(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,edges1,edges2;
        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(x==11-l+1){
                printf("%d %d %d | %d %d NASO111\n",pom.ff,pom.ss.ff,pom.ss.ss,niz[1].ff,niz[1].ss);
            }*/
            edges1.pb(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];
            //printf("%d RADIO\n",x);

            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(x==11-l+1){
                printf("%d %d %d | %d %d NASO\n",pom.ff,pom.ss.ff,pom.ss.ss,niz[1].ff,niz[1].ss);
            }*/
            edges2.pb(pom);
            dodaj_comp(cand[i],d,l);
        }

        reverse(edges2.begin(),edges2.end());
        for(int i=0;i<edges1.size();i++){
            edges1[i]=min(edges1[i],edges2[i]);
            ///printf("%d %d %d | %d %d %d EDGES\n",edges1[i].ff,edges1[i].ss.ff,edges1[i].ss.ss,edges2[i].ff,edges2[i].ss.ff,edges2[i].ss.ss);
            if(edges1[i].ss.ff!=-1)edges.pb(edges1[i]);
        }

        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+l-1,v+l-1,w);
            ret+=w;
            d.join(u,v);
        }
        ///printf("END ITER\n");
       /// break;
       ccc++;

    }
    ///printf("%d CCC\n",ccc);

    return ret;
}

int check(int l,int r){

    vector<pair<int,pii>>edges;
    for(int i=l;i<=r;i++){
        for(int j=l+1;j<=r;j++){
            edges.pb({ divs[i*j/__gcd(i,j)].size(),{i-l+1,j-l+1} });
        }
    }
    sort(edges.begin(),edges.end());
    dsu d(r-l+1);
    int ret=0;
    for(int i=0;i<edges.size();i++){
        int u,v,w;
        u=edges[i].ss.ff;
        v=edges[i].ss.ss;
        w=edges[i].ff;
        if(d.root(u)==d.root(v))continue;
        printf("%d %d | %d\n",u+l-1,v+l-1,w);
        d.join(u,v);
        ret+=w;
    }
    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;
}