uses crt;
var duyet:array[0..100000000] of boolean;
    i,k,a,b,j,jj,d,max:longword;
begin
    clrscr;
    readln(k);
    fillchar(duyet,sizeof(duyet),true);
    duyet[0]:=false;duyet[1]:=false;
    max:=2;
    for i:=1 to k do
      begin
          readln(a,b);
          if b>max then
             begin
                 for j:=max to trunc(sqrt(b)) do
                     if duyet[j]=true then
                         for jj:=0 to (b-j*j) div j do
                             duyet[j*j+jj*j]:=false;
                 max:=b;
             end;
          d:=0;
          for j:=a to b do
             if duyet[j]=true then inc(d);
          writeln(d);
      end;
readln;
end.

uses crt;
var i,n,a,b,g:longint; l:array[1..1000000]of longint;  
function nt(a:longint):boolean;
var i:longint;
begin
   i:=2;
   while(a>1)and(a mod i<>0)do inc(i);
   nt:=i=a;
end;
begin
   readln(n); 
   for g:=1 to n do 
      begin
         readln(a,b);
         for i:=a to b do 
            if nt(i) then inc(l[g]);
      end; 
   for i:=1 to n do 
      writeln(l[i]);
end.