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

const int M=1e6+10;

int dis[M],mn[M];
bool mk[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].emplace_back(i);
	for(int i=1;i<=1e6;++i)mn[i]=dis[i]=1e9;

	int q;
	scanf("%d",&q);
	priority_queue<pair<int,int>>que;
	while(q--){
		int l,r;
		scanf("%d%d",&l,&r);
		int ans=0;
		que.emplace(0,l);
		dis[l]=0;
		while(!que.empty()){
			auto [d,x]=que.top();
			que.pop();
			if(mk[x])continue;
			ans+=dis[x],mk[x]=1;
			for(int y:G[x]){
				if(mn[y]>w[x]){
					mn[y]=w[x];
					for(int i=((l-1)/y+1)*y;i<=r;i+=y){
						if(mk[i])continue;
						if(dis[i]>w[i]+w[x]-w[y]){
							dis[i]=w[i]+w[x]-w[y];
							que.emplace(-dis[i],i);
						}
					}
				}
			}
		}
		for(int i=l;i<=r;++i){
			dis[i]=1e9,mk[i]=0;
			for(int x:G[i])mn[x]=1e9;
		}
		printf("%d\n",ans);
	}
}