#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll primo[1000000];
ll vetor[1000000];

int qtdP(ll primo[],ll i){
    if(i==1||i==0){
        return 0;
    }
    if(i==2){
         return primo[2];
    }
    return primo[i]+primo[i-1];
}

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;
        if(a==b){
            a = sqrt(a);
            s = vetor[a]-vetor[a-1];
        }else{
            auxiliar = a;
            a = sqrt(a);
            b = sqrt(b);
            s = vetor[b]-vetor[a];
        }
        cout<<s<<"\n";
        t--;
    }

}