#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
bool l[100005];
int a[1005],b[1005],ma;
int k;
int main()
{

cin>>k;
for(int i=1;i<=k;i++)
{
    scanf("%d",&a[i]);
    scanf("%d",&b[i]);
    if(ma<b[i])ma=b[i];
}
    for(int i=2;i<=ma;i++)
    {
        int x=0;
        for(int j=2;j*j<=i;j++)
        {
            if(i%j==0){x=1;break;}
        }
        if(x==0)l[i]=1;
        }
    for(int i=1;i<=k;i++)
     {
         int br=0;
         for(int j=a[i];j<=b[i];j++)
         if(l[j]==1)br++;
         cout<<br<<endl;
     }

return 0;
}
