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

const int M=1e6+10;

int mx[M][21],tmx[M][21];
vector<pair<int,int>>Q[M];
vector<int>G[M];
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	vector<int>w(M);
	for(int i=2;i<=1e6;++i)if(!w[i])
	   	for(int j=i;j<=1e6;j+=i)w[j]++;
	for(int i=1;i<=1e6;++i)
		for(int j=i;j<=1e6;j+=i)
			G[j].push_back(i);
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		for(int x:G[l])mx[x][w[l]]=1;
		int res=0;
		for(int i=l+1;i<=r;++i){
			int t=1e9;
			for(int x:G[i]){
				for(int j=w[x];j<=20;++j)
					if(mx[x][j])t=min(t,j-w[x]);
				mx[x][w[i]]=1;
			}
			res+=t+w[i];
		}
		for(int i=l;i<=r;++i)
			for(int x:G[i])mx[x][w[i]]=0;
		cout<<res<<"\n";
	}
}