#include
using namespace std;
int main(int argc, char const *argv[])
{ int n=10001;
int sieve[10001] = {0};
for(int i=1; i<n; i=i+2){
sieve[i]=1;
}
sieve[0]=0;
sieve[1]=0;
sieve[2]=1;
for (int i = 3; i < 100; i+=2)
{ if(sieve[i]!=0){
for (int j = i*2; j < n; j+=i)
{
sieve[j]=0;
}
}
}
//optimization
for (int i = 3; i < 100; i+=2)
{ if(sieve[i]!=0){
for (int j = ii; j < n; j+=i2)
{
sieve[j]=0;
}
}
}
int t,p=0;
cin>>t;
while(p<t){
// print prime no. from a to b
int a, b,count=0;
cin>>a>>b;
for (int i = a; i <=b ; i++)
{
if(sieve[i]){
count++;
}
}
cout<<count<<endl;
p++;
}
return 0;
}