#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn =1e6+12 , N = 1e6 , inf = 1e9 , mod = 1000000007 ;
int t[maxn] , a[maxn] , mark[maxn] , par[maxn] , s[maxn] , o[maxn] , dp[maxn] ;
vector <int> vec[maxn] ; 
vector <pii> ed[maxn] ;

int find(int v){
	if(par[v]==0)return v; 
	return par[v] = find(par[v]);
}

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);
	for(int i = 1; i <= N ; i++)a[i] = 1;
	for(int i = 2; i <= N ; i++){
		if(mark[i] == 1)continue ;
		for(int j = i ; j <= N ; j+=i){
			mark[j] = 1 ;
			a[j] *= i ;
			o[j] = i ;
			t[j]++;
		}
	}
	int T ;cin >> T ;
	for(int i = 1; i <= T ; i++){
		for(int i =0 ; i <= 30 ; i++){
			ed[i].clear() ;
		}
		int l  ,r ;
		cin >> l >> r ;
		for(int i = l ; i <= r ;i++){
			s[i] = 1; par[i] =0  ;
			int x=  a[i] ;
			vector <int> v ;
			while(x!=1){
				v.pb(o[x]);x/=o[x]; 
			}
			dp[0] = 1;
			vec[1].pb(i);
			for(int j = 1 ; j < (1<<sz(v));  j++){
				int id = __builtin_ctz(j) ;
				dp[j] = dp[j^(1<<id)] * v[id] ;
				vec[dp[j]].pb(id);
			}
		}
		for(int i = 1; i <=r ; i++){
			if(sz(vec[i]) == 0)continue ;
			int mn = inf , id ;
			for(int z : vec[i]){
				if(mn > t[a[z]/i]){
					id= z ;
					mn = t[a[z]/i];
				}
			}
			for(int z : vec[i]){
				ed[mn+t[z]].pb({id ,z});
			}
		}
		int ans =0 ;
		for(int i =0; i <= 30 ; i++){
			for(pii x : ed[i]){
				if(find(x.F) != find(x.S)){
					x.F = find(x.F) ; x.S = find(x.S);
					if(s[x.F] > s[x.S])swap(x.F , x.S) ;
					par[x.F] = x.S ;
					s[x.S] += s[x.F];
					ans += i ;
				}
			}
		}
		cout << ans << "\n"; 
		for(int i = 1 ; i <= r ; i++){
			vec[i].clear(); 
		}

	}
}
/*


*/