#include <iostream>
using namespace std;

const int M=1000;
const int N=M*M+1;

//   i   e[i]   0
//   i     e[i]   1
int e[N] = {1,1,0,0}; // 0  1   
                      // 2  3   
int primecnt[N];


int main()
{ //    2
  for(int i=4; i<N; i=i+2) e[i]=1; 
  
  int p=3;
  while(p<M)
  { // p    
    
    //    p
    for(int k=2*p; k<N; k=k+p) e[k] = 1; 
    
    //     
    p=p+2; while(e[p]==1) p=p+2; 
  }
  
  for(int i=2; i<N; i++)
    if(e[i]==0) primecnt[i]=primecnt[i-1]+1;
    else primecnt[i]=primecnt[i-1];
  
  int k,a,b;
  cin >> k;
  for(int i=0; i<k; i++)
  { cin >> a >> b;
    cout << primecnt[b]-primecnt[a-1] << endl;
  }
  
  return 0;
}
