#include<bits/stdc++.h>
using namespace std;
int p[2000005],sum[2000005];
int t,a,b;
int main()
{
    freopen("prime.in", "r", stdin);
    freopen("prime.out", "w", stdout);
    for(int i=2; i*i<2000005; i++)
        if(p[i]==0)//从未判断过 
        {
            for(int j=i*2; j<2000005; j+=i)//因为按照题目，不允许出现一个质数的平方及以上，所以必须排除 
                if(p[j]==0) //没遇到 
                    p[j]=1;//改成符合规范的数 
            for(long long j=(long long)i*i; j<2000005; j+=i*i)//还有一种情况，符合没有质数平方，但是立方 
                p[j]=2;//标记另一种情况 
        }
    for(int i=2; i<2000005; i++)
        if(p[i]==1)
            sum[i]=sum[i-1]+1;//符合规范，加上 
        else
            sum[i]=sum[i-1];//否则不变 
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d", &a, &b);
        printf("%d\n",sum[b]-sum[a-1]);//就是第 b 个数组的数减去 a-1 个数组的数 
    }
    return 0;
}