#include<bits/stdc++.h>
using namespace std;
int m[80000],kk=0,h,a,b;
int main()
{
for(int i=2;i<=1000000;i++)
{
int f=0;
for(int j=2;j*j<=i;j++)
if(i%j==0)
{
f=1;
break;
}
if(f==0)
{
kk++;
m[kk]=i;
}
}
int k,u=0;
cin>>k;
while(u<k)
{
u++;
scanf("%d%d",&a,&b);
h=1;
while(m[h]<a&&h<=kk)
{
if(m[h+1000]<a&&h+1000<=kk)h+=1000;
else h++;
}
int hh=h;
h=1;
while(m[h]<b&&h<=kk)
{
if(m[h+1000]<b&&h+1000<=kk)h+=1000;
else h++;
}
if(m[h]!=b)h--;
if(h<hh||h==hh)
{
if(h<hh)cout<<0<<endl;
else cout<<1<<endl;
continue;
}
cout<<h-hh+1<<endl;
}
return 0;
}