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

#define maxn 1000006
typedef long long int ll;


vector<ll>prime;
int mark[maxn];

void sieve()
{
    prime.push_back(2);
    for(int i=4; i<maxn; i+=2)
    {
        mark[i]=1;
    }
    for(int i=3; i*i<maxn; i+=2)
    {
        if(mark[i]==0)
        {
            for(int j=i*i; j<maxn; j+=(2*i))
            {
                mark[j]=1;
            }
        }
    }

    for(int i=3; i<maxn; i+=2)
    {
        if(!mark[i])
        {
            prime.push_back(i);
        }
    }

}

int main()
{
    sieve();
    ll i,j,k,l,r,a;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %lld",&l,&r);
        ll cnt=0;
        for(i=0; prime[i]*prime[i]<=r; i++)
        {
            a=prime[i]*prime[i];
            while(a<=r)
            {
                if(a>=l)
                    cnt++;
                a=a*prime[i];
            }
        }
        printf("%lld\n",cnt);
    }
    return 0;
}