#include<iostream>
#include<set>
#include<stack>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<memory.h>
#include<queue>
#define ll long long
using namespace std;
const int N = 5000000;
ll lp[N+1];
ll a[N+1];
int main()
{
memset(lp,0,sizeof(lp));
vector<int> pr;

for (int i=2; i<=N; ++i) {
	if (lp[i] == 0) {
		lp[i] = i;
		pr.push_back (i);
	}
	for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
		lp[i * pr[j]] = pr[j];
}
    memset(a,0,sizeof(a));
    for(int i=1;i<=N;i++)
    {
        if(!lp[i]) a[i] = 1; else a[i] = a[i/lp[i]] + a[lp[i]];
    }
    for(int i=2;i<=N;i++)
        a[i]+=a[i-1];
        a[0] = 0;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        cout<<a[x]-a[y]<<endl;
    }


}