const maxn=1000000;
var u:array[1..10000000]of boolean;
    s:array[0..10000000]of int64;
    i,m,x1,y1,x2,y2:longint;
    now:int64;
Procedure prime(n:longint);
  var i,j:longint;
begin
  for i:=2 to n do
    if not u[i] then begin
      j:=i+i;
      while j<=n do begin
        u[j]:=true;
        inc(j,i);
      end;
    end;
end;
begin
  prime(maxn);
  s[1]:=0; s[2]:=0;
  now:=0;
  for i:=3 to maxn do begin
   if u[i]=false then inc(now);
   s[i]:=now;
  end;
  readln(m);
  for i:=1 to m do begin
  readln(x1,y1,x2,y2);
  writeln((s[x2]-s[x1-1])*(s[y2]-s[y1-1])) ;
  end;
  close(input);
  close(output);
end.