#include <bits/stdc++.h>#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using i64 = long long;
const int N = 1e6 + 5;
int sum[N];
int num[N];
vector<int>isp(N,1);
vector<int>bas(N,1);
vector<int>sz(N),vis(N);
vector<int>u[N];
int check(int x,int y) {
	return num[x]+num[y]-num[__gcd(x,y)];
}
void Euler_prime(int n){
	isp[0] = 0;
	isp[1] = 0;
	for ( int i = 2 ; i <= n ; i++ ) {
		if ( !isp[i] ) continue;
		for ( int j = 1; i*j <= n ; j++ ) {
			num[i*j]++;
			bas[i*j] *= i;
			if ( j != 1 ) isp[i*j] = 0;
			u[i*j].emplace_back(i);
		}
	}
	for ( int i = 1 ; i <= n ; i++ ) {
		sum[i] += sum[i-1]+isp[i];
	}
} 
void solve() {
	int l,r;
	cin >> l >> r;
	if ( l == 1 ) {
		int res = 0;
		for ( int i = 2 ; i <= r ; i++ ) {
			res += num[i];
		}
		cout << res << '\n';
		return;
	}
	int t = sum[r]-sum[l-1];
	i64 ans = 0;
	if ( t ) {
		for (int i=1;i<=r;++i) sz[i]=vis[i]=0;
		for (int i=l;i<=r;++i) ++sz[bas[i]];
		for (int i=2;i<=r;++i) if (!vis[i]&&sz[i])
		{
			ans+=num[i]*(sz[i]-1)+(num[i]+1); vis[i]=1;
			for (int j=i*2;j<=r;j+=i) if (!vis[j]&&sz[j])
			vis[j]=1,ans+=num[j]*sz[j];
		}
		ans -= 2;
	} else {
		int n = r-l+1;
		vector<int>dis(n,1e9);
		dis[0] = 0;
		int idx = 0;
		vector<int>f(n,0);
		for ( int i = 1 ; i < n ; i++ ) {
			int mx = 1e9;
			int id = 0;
			f[idx] = 1;
			for ( int j = 0 ; j < n ; j++ ) {
				if ( f[j] ) continue;
				dis[j] = min(dis[j],dis[idx]+check(idx+l,j+l));
				if ( dis[j] < mx ) {
					mx = dis[j];
					id = j;
				}
			}
			ans += dis[id];
			dis[id] = 0;
			idx = id;
		}
	}
	cout << ans << '\n';
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	Euler_prime(1000000);
	int T = 1;
	cin >> T;
	while ( T-- ) {
		solve();
	}
}

// 1 2 3
// 1 2 3
// 1 2 3

using namespace std;
using ull = unsigned long long;
using i64 = long long;
const int N = 1e6 + 5;
int sum[N];
int num[N];
vector<int>isp(N,1);
vector<int>bas(N,1);
int check(int x,int y) {
	return num[x]+num[y]-num[__gcd(x,y)];
}
void Euler_prime(int n){
	isp[0] = 0;
	isp[1] = 0;
	for ( int i = 2 ; i <= n ; i++ ) {
		if ( !isp[i] ) continue;
		for ( int j = 1; i*j <= n ; j++ ) {
			num[i*j]++;
			if ( j != 1 ) isp[i*j] = 0;
			bas[i*j] *= i;
		}
	}
	for ( int i = 1 ; i <= n ; i++ ) {
		sum[i] += sum[i-1]+isp[i];
	}
} 
void solve() {
	int l,r;
	cin >> l >> r;
	if ( l == 1 ) {
		int res = 0;
		for ( int i = 2 ; i <= r ; i++ ) {
			res += num[i];
		}
		cout << res << '\n';
		return;
	}
	int t = sum[r]-sum[l-1];
	i64 ans = 0;
	if ( t ) {
		vector<int>vis(r+1,1);
		map<int,int>mp;
		for ( int i = l ; i <= r ; i++ ) {
			mp[bas[i]]++;
		}
		int cnt = 0;
		for ( auto [i,k] : mp ) {
			for ( int j = 2 ; i*j <= 1000000 ; j++ ) {
				if ( mp.contains(i*j) ) {
					ans += num[i*j]*mp[i*j];
					mp.erase(i*j);
				}
			}
			ans += k*num[i];
			cnt++;
		}
		ans += cnt-2;
	} else {
		int n = r-l+1;
		vector<int>dis(n,1e9);
		dis[0] = 0;
		int idx = 0;
		vector<int>f(n,0);
		for ( int i = 1 ; i < n ; i++ ) {
			int mx = 1e9;
			int id = 0;
			f[idx] = 1;
			for ( int j = 0 ; j < n ; j++ ) {
				if ( f[j] ) continue;
				dis[j] = min(dis[j],dis[idx]+check(idx+l,j+l));
				if ( dis[j] < mx ) {
					mx = dis[j];
					id = j;
				}
			}
			ans += dis[id];
			dis[id] = 0;
			idx = id;
		}
	}
	cout << ans << '\n';
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	Euler_prime(1000000);
	int T = 1;
	cin >> T;
	while ( T-- ) {
		solve();
	}
}

// 1 2 3
// 1 2 3
// 1 2 3

answer.code:1:25: warning: extra tokens at end of #include directive
    1 | #include <bits/stdc++.h>#include <bits/stdc++.h>
      |                         ^
answer.code:97:11: error: redefinition of ‘const int N’
   97 | const int N = 1e6 + 5;
      |           ^
answer.code:5:11: note: ‘const int N’ previously defined here
    5 | const int N = 1e6 + 5;
      |           ^
answer.code:98:5: error: redefinition of ‘int sum [1000005]’
   98 | int sum[N];
      |     ^~~
answer.code:6:5: note: ‘int sum [1000005]’ previously declared here
    6 | int sum[N];
      |     ^~~
answer.code:99:5: error: redefinition of ‘int num [1000005]’
   99 | int num[N];
      |     ^~~
answer.code:7:5: note: ‘int num [1000005]’ previously declared here
    7 | int num[N];
      |     ^~~
answer.code:100:12: error: redefinition of ‘std::vector<int> isp’
  100 | vector<int>isp(N,1);
      |            ^~~
answer.code:8:12: note: ‘std::vector<int> isp’ previously declared here
    8 | vector<int>isp(N,1);
      |            ^~~
answer.code:101:12: error: redefinition of ‘std::vector<int> bas’
  101 | vector<int>bas(N,1);
      |            ^~~
answer.code:9:12: note: ‘std::vector<int> bas’ previously declared here
    9 | vector<int>bas(N,1);
      |            ^~~
answer.code:102:5: error: redefinition of ‘int check(int, int)’
  102 | int check(int x,int y) {
      |     ^~~~~
answer.code:12:5: note: ‘int check(int, int)’ previously defined here
   12 | int check(int x,int y) {
      |     ^~~~~
answer.code:105:6: error: redefinition of ‘void Euler_prime(int)’
  105 | void Euler_prime(int n){
      |      ^~~~~~~~~~~
answer.code:15:6: note: ‘void Euler_prime(int)’ previously defined here
   15 | void Euler_prime(int n){
      |      ^~~~~~~~~~~
answer.code:120:6: error: redefinition of ‘void solve()’
  120 | void solve() {
      |      ^~~~~
answer.code:31:6: note: ‘void solve()’ previously defined here
   31 | void solve() {
      |      ^~~~~
answer.code:176:5: error: redefinition of ‘int main()’
  176 | int main() {
      |     ^~~~
answer.code:79:5: note: ‘int main()’ previously defined here
   79 | int main() {
      |     ^~~~