#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e6+5;
bool pr[MAXN],sqf[MAXN];
int omega[MAXN];
vector<int> divi[MAXN];

void solve(int t){
    int l,r;
    cin>>l>>r;
    
    auto reduce = [](int x,int y)->int{
        while(__gcd(x,y)>1){
            x/=__gcd(x,y);
        }
        return x;
    };
    
    auto cost = [&](int x,int y)->int{
        int gcd= __gcd(x,y);
        x = reduce(x,gcd);
        y = reduce(y,gcd);
        
        return omega[gcd]+omega[x]+omega[y];
    };
    
    vector<int> best(r+1);
    for(int i=1;i<=r;i++){
        best[i]=-1;
        if(i!=1 && !pr[i])continue;
        for(int j=(l+i-1)/i*i;j<=r;j+=i){
            if(best[i]==-1 || omega[reduce(best[i],j)]>omega[reduce(j,i)]){
                best[i]=j;
            }
        }
    }

    vector<array<int,3>> v;
    for(int i=l;i<=r;i++){
        for(auto x : divi[i]){
            if(best[x]!=-1)v.push_back({i,best[x],cost(i,best[x])});
        }
    }
    
    int ans=0;
    vector<int> ds(r+1);
    for(int i=l;i<=r;i++){
        ds[i]=i;
    }
    
    auto f = [&](auto &f,int x)->int{
        if(ds[x]!=x)return ds[x]=f(f,ds[x]);
        return x;
    };
    
    auto add = [&](int x,int y)->bool{
        int a = f(f,x), b = f(f,y);
        
        if(a==b)return false;
        
        ds[a]=b;
        return true;
    };
    
    sort(v.begin(),v.end(),[](auto x,auto y){return x[2]<y[2];});
    
    for(auto [i,j,cost] : v){
        if(add(i,j)){
            //cout<<i<<" "<<j<<" "<<cost<<"\n";
            ans+=cost;
        }
    }
    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    memset(pr,true,sizeof pr);
    for(long long i=2;i<MAXN;i++){
        if(pr[i]){
            for(int j=i;j<MAXN;j+=i){
                omega[j]++;
                pr[j]=false;
            }
            for(int j=i;j<MAXN;j+=i)divi[j].push_back(i);
        }
        
        divi[i].push_back(1);
    }
    
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)solve(i);
    
    return 0;
}