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