#include "bits/stdc++.h"
using namespace std;
 
const int N = 5e6 + 5;
 
int h[N];
vector < int > spf, primes;
 
void RunLinearSieve() {
	int n = N;
	spf.assign(n + 1, 0);
	for(int i = 2; i < n; ++i) {
		if(!spf[i]) {
			spf[i] = i;
			primes.push_back(i);
		}
		for(int x : primes) {
			int calc = i * x;
			if(x > spf[i] || calc > n) {
				break;				
			}
			spf[calc] = x;
		}
	}
	primes.clear();
	for (int j = 2; j < N; ++j) {
		int let = j, cnt(0);
		while (let != 1) {
			let /= spf[let];
			++cnt;
		}
		h[j] = cnt + h[j-1];
	}
}
inline void solve() {
	int a, b;
	cin >> a >> b;
	if (a == b) {
		cout << "0\n";
		return;
	}
	int t = a - b;
	cout << h[a] - h[a-t] << '\n';
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    RunLinearSieve();
    cin >> t; while(t--)
                solve();
    return 0;
}