#include<bits/stdc++.h>
#define MAX 1000009
#define lim 1000000000000
 
using namespace std;
 
bool arr[MAX];
 
vector<int>prime;
 
vector<long long>check;
 
void sieve()
{
    long long i,j,k;
 
    k= sqrt(MAX);
 
    prime.push_back(2);
 
    for(i=3; i<=k; i+=2)
    {
        if(arr[i]==0)
        {
            for(j=i*i; j<MAX; j+=i+i)
            {
                arr[j]=1;
            }
        }
    }
 
    for(i=3; i<MAX; i+=2)
        if(arr[i]==0)
            prime.push_back(i);
}
 
int main()
{
    sieve();
 
    int sz = prime.size(),test,i,j;
 
    for(i=0; i<sz; i++)
    {
        for(j=2;; j++)
        {
            long long store = pow(prime[i],j);
 
            if(store<=lim)
            {
                check.push_back(store);
            }
            else
                break;
        }
    }
 
    sort(check.begin(),check.end());
 
    long long low,high,res;
 
    scanf("%d",&test);
 
    while(test--)
    {
        scanf("%lld%lld",&low,&high);
 
        vector<long long>::iterator from,to;
 
        from = lower_bound(check.begin(),check.end(),low);
 
        to = upper_bound(check.begin(),check.end(),high);
 
        res = (to-check.begin())-(from-check.begin());
 
        printf("%lld\n",res);
    }
 
    return 0;
}