#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll primo[1000000];
ll vetor[1000000];
int main() {
    //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(int j = 2*i;j<=1000000;j+=i){
                primo[j] = 0;
            }
        }
    }
    int t;
    ll a, b, s = 0;
    cin>>t;
    ll aux;
    while(t>0){
        cin>>a>>b;
        s = 0;
        ll aa = a;
        a = sqrt(a);
        if(pow(a,2)!=aa) a++;
        b = sqrt(b);
        for(ll i= a;i<=b;i++){
            if(primo[i])s++;
        }
        cout<<s<<"\n";
        t--;
    }
}