#include<bits/stdc++.h>
using namespace std;
int main()
{
 vector <bool> f(100005,true);
 vector <int> a(100005,0);
 f[1]=false;
 for (int i=2;i*i<=100005;i++)
 if ( f[i] )
  for (int y=i*i; y<=100005;y+=i) f[y]=false;
 for (int i=2;i<=100005;i++) 
 if ( f[i] ) a[i]=a[i-1]+1;
 else a[i]=a[i-1];
 int q;
 cin>>q;
 while(q--)
 {
  int l,r;
  cin>>l>>r;
  cout<<a[r]-a[l-1]<<"\n";
 }
}

#include <bits/stdc++.h>
using namespace std;
bool a[100000]; 
void sangnt(int n){
 for (int i=2; i*i<=n; i++) 
    for (int j=2; i*j<=n; j++)
     a[i*j]=1; 
}
int main()
{
 int t,max=0;
 cin>>t;
 int l[t],r[t];
 for (int i=1; i<=t; i++){
  cin>>l[i]>>r[i];
  if (r[i]>max) max=r[i];
 }
 sangnt(max);
 for (int i=1; i<=t; i++){
  int d=0;
  for (int j=l[i]; j<=r[i]; j++) 
     if (!(a[j])) d=d+1;
  cout<<d<<endl;
 }
}