PRIMECOUNT

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

const int N = 1050;

int64_t segmentedSieveNoPreGen(int64_t L, int64_t R) {
    vector<bool> isPrime(R - L + 1, true);
    int64_t lim = sqrt(R);
    int64_t ans = 0;
    for(int64_t i = 2; i <= lim; ++i)
        for(int64_t j = max(i * i, (L + i - 1) / i * i); j <= R; j += i)
            if(isPrime[j - L])
                isPrime[j - L] = false,
                ans++;

    if(L == 1)
        isPrime[0] = false,
        ans++;

    ans = (R - L + 1) - ans;
    return ans;
}

int t;
int64_t L, R;

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#else
    freopen("PRIMECOUNT.inp", "r", stdin);
    freopen("PRIMECOUNT.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> t;
    while(t--) {
        cin >> L >> R;
        cout << segmentedSieveNoPreGen(L, R) << '\n';
    }

    return 0;
}