#include <bits/stdc++.h>
#include <cstdint>
using namespace std;
typedef long long ll;
 
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
 
#define PB push_back
#define MP make_pair
#define FOR for(long long i = 0;i<n;i++)
#define SP << " " <<
#define F first
#define S second
 
#define MOD 1000000007
#define max_n 5000005
#define lMOD 1e16
int a1[1000005], b1[1000005];
int n;
ll p[max_n];
ll f[max_n];
void solve(){
	cin >> n;

	FOR cin >> a1[i] >> b1[i];

	for(int i = 2; i<5000001; i++){
		if (f[i]!=0) continue; f[i] = 1;
		for(int j = 2*i; j<5000001; j+=i){
			ll te = j;
			while(te%i ==0){
				te/=i;
				f[j]++;
			}
		}
	}
	p[0] = 0;
	for(int i = 1; i<max_n; i++){
		p[i] = p[i-1] + f[i];
	}
	for(int i = 0; i< n; i++){
		cout << p[a1[i]]- p[b1[i]] << endl;
	}
}


int main() {
#ifndef ONLINE_JUDGE

	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);

#endif
	long long t;
	t = 1;
	// cin >> t;
	while (t--) {
	solve();
	}
	return 0;
}