uses crt;
const MAX = 10000000;
var sieve: array[2..MAX] of boolean;
    count: array[0..MAX] of longint;
    i,n,l,r: longint;
procedure countPrime;
var i,j: longint;
begin
    sieve[2] := true;
    for i := 3 to MAX do
        if i mod 2 = 0 then sieve[i] := false else sieve[i] := true;
    i := 3;
    while i*i <= MAX do
    begin
        j := i*i;
        while j <= MAX do
        begin
            sieve[j] := false;
            j := j + 2*i;
        end;
        i := i + 2;
    end;
    count[0] := 0;
    count[1] := 0;
    for i := 2 to MAX do
        if sieve[i] then count[i] := count[i - 1] + 1
        else count[i] := count[i - 1];
end;
begin
    assign(input, 'DOANNT.INP'); reset(input);
    assign(output, 'DOANNT.OUT'); rewrite(output);
    countPrime();
    readln(n);
    for i := 1 to n do
    begin
        readln(l, r);
        if sieve[r] then writeln(count[r] - count[l] + 1)
        else writeln(count[r] - count[l]);
    end;
end.