#include <iostream>
using namespace std;
int main()
{
long long a;
cin>>a;
long long b[a],c[a],br[a],i,j,l;
int zn;
for(i=0;i<=a-1;i++)
{
br[i]=0;
cin>>b[i]>>c[i];
if(b[i]==1) b[i]=2;
for(j=b[i];j<=c[i];j++)
{zn=0;
for(l=2;l<=(j/2+j%2);l++)
if(j%l==0) zn=1;
if(zn==0) br[i]+=1;
}
}
for(i=0;i<=a-1;i++)
cout<<br[i]<<endl;
return 0;
}