#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;
}