#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;
long long a[1005],b[1005],k,s[1000005],i,j,fl,maxn,br;
int main()
{
    cin>>k;
    for(i=1;i<=k;i++)
    {
        scanf("%lld",&a[i]);
        scanf("%lld",&b[i]);
        maxn=max(maxn,b[i]);
    }
    for(i=2;i<=maxn;i++)
    {
        fl=0;
        br=0;
        for(j=1;j<=i;j++)
        {
            if(i%j==0)br++;
            if(br==3){fl=1;break;}
        }
        if(fl==0)s[i]=s[i-1]+1;
        else s[i]=s[i-1];
    }
    for(i=1;i<=k;i++)
    {
        cout<<s[b[i]]-s[a[i]-1]<<endl;
    }
    return 0;
}