#include <cstdlib>
#include <iostream>
using namespace std;
bool jeProst(int x){
int brojac=0;
for(int i =2;i<x;i++)
if(x%i==0) brojac++;
if(brojac==0 && x!=1) return true;
return false;}
int main(){
int k,a,b,i,brojac(0);
cin>>k;
for(i=0;i<k;i++)
{brojac=0;
cin>>a>>b;
for(int j=a;j<=b;j++)
if(jeProst(j))brojac++;
cout<<brojac<<endl;}
cout<<endl;
system(„PAUSE“);
return EXIT_SUCCESS;
}