#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll primo[1000000];
ll vetor[1000000];
int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //fazendo crivo
    for(ll i = 2;i<=1000000;i++){
        primo[i]=1;
    }
    for(ll i = 2;i<=1000000;i++){
        if(primo[i]){
            for(ll j = 2*i;j<=1000000;j+=i){
                primo[j] = 0;
            }
        }
    }
    int aux = 0;
    for(ll i = 0;i<=1000000;i++){
        if(primo[i]) aux++;
        vetor[i] = aux;
    }
    int t;
    ll auxiliar, a, b, s = 0;
    cin>>t;
    while(t>0){
        auxiliar = 0;
        cin>>a>>b;
        s = 0;
        a = sqrt(a-1);
        b = sqrt(b);
        s = vetor[b]-vetor[a];
        cout<<s<<"\n";
        t--;
    }
}