Untitled

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

long long pr[10000001];

void sangsnt(){
    pr[0] = pr[1] = 1;
    for(long long i = 2; i <= sqrt(10000001); i++){
        if(pr[i] == 0){
            for(long long j = i * i; j < 10000001; j += i){
                pr[j] = 1;
            }
        }
    }
}

int main() {
    sangsnt();
    long long q;
    cin >> q;
    while(q--){
        long long L,R;
        cin >> L >> R;
        long long dem = 0;
        for(long long i = L; i <= R; i++){
            if(pr[i] == 0){
                dem++;
            }
        }
        cout << dem << "\n";
    }   
}