NIGERIAN

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll SieveOfEratosthenes(ll n)
{   ll cnt;
    bool prime[n+1];
    memset(prime, true, sizeof(prime));

    for (ll p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (ll i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
    for (ll p=2; p<=n; p++)
       if (prime[p]) cnt++;

    return cnt;
}


int main()
{   ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll q; cin >> q;

    while(q--){
        ll l,r; cin >> l >> r;
        if(r>l){
            cout << SieveOfEratosthenes(r)-SieveOfEratosthenes(l) << "\n";
        }
        if(l>=r){
             cout << SieveOfEratosthenes(l)-SieveOfEratosthenes(r) << "\n";
        }
    }

    return 0;
}