#pragma GCC optimize("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int Lim = 1e6;
vector<int> pr;
vector<int> lpf;
void Linear_sieve(int n = Lim) {
    pr.assign(1, 2);
    lpf.assign(n + 1, 2);

    for (int x = 3; x <= n; x += 2) {
        if (lpf[x] == 2) pr.push_back(lpf[x] = x);
        for (int i = 1; i < pr.size() && pr[i] <= lpf[x] && pr[i] * x <= n; ++i)
            lpf[pr[i] * x] = pr[i];
    }
}

int query(int l, int r) {
    int res = 0;
    
    for (int x: pr) {
        res += (l <= x && x <= r);
    }
    if (l < Lim) l = Lim;
    if (l > r) return res;
    
    vector<bool> prime(r - l + 1);
    for (int x: pr) {
        for (int i = ((l - 1) / x + 1) * x; i <= r; i += x)
            prime[i - l + 1] = true;
    }
    
    for (int i = l; i <= r; ++i) res += (prime[i - l + 1] == 0);
    return res;
}

int main() {
    Linear_sieve();
    int t, l, r;
    cin >> t;
    while (t--) {
        cin >> l >> r;
        cout << query(l, r) << "\n";
    }
}

#include <bits/stdc++.h>

using namespace std;

long long t, l, r;

long long sl(long long l, long long r){
    long long c = 0;
    vector<bool> snt((r-l+1),true);
    for (long long i=2; i*i<=r; i++){
        for (long long j=max(i*i, (l+i-1)/i*i); j<=r; j+=i){
            snt[j-l] = false;
        }
    }
    if (l<=1){
        snt[1-l] = false;
    }
    for (long long i=l; i<=r; i++){
        if (snt[i-l]){
            c++;
        }
    }
    return c;
}

int main(){
    cin >> t;
    for (long long i=0; i<t; i++) {
        cin >> l >> r;
        cout << sl(l,r) << endl;
    }
}

$\color{red}{\text{#Daoanhviet96}}$