#include<iostream>
#include<cmath>
#include<cstdio>
#include<string>
#include<stack>
#include<algorithm>
using namespace std;
long long k,z[1000001],br,x,i,i1,j,a,b,q,ans[1001];
int main()
{
   cin>>k;
   for(i=1; i<=k; i++)
   {
      cin>>a>>b;
      for(j=a; j<=b; j++)
      {
         
         if(z[j]==2) 
         {
            br++;
            
         }
         if(z[j]==0)
         {
            if(j!=1)
            for(i1=2; ; i1++)
            {
               
              if(j%i1==0&&j!=2)
              {
                 x=1;
                 break;
              } 
              if(i1*i1>=j) break; 
            }
            if(x==1) z[j]=1;
            if(x==0&&j!=1)
            {
               br++;
               z[j]=2;
            }
            x=0;
         }
      }
      ans[q]=br;
      br=0;
      q++;
   }
   for(i=0; i<=q-1; i++)
   cout<<ans[i]<<endl;
   return 0;
}
