1 uses math; 2 const maxn=55000; 3 var i,n,a,b,c,d,w,tot:longint; 4     ans:int64; 5     sum,mu,p:array[0..maxn] of int64; 6 procedure get; 7  var i,j,k:longint; 8      check:array[0..maxn] of boolean; 9  begin10  fillchar(check,sizeof(check),false);11  tot:=0;mu[1]:=1;12  for i:=2 to maxn do13   begin14    if not(check[i]) then begin inc(tot);p[tot]:=i;mu[i]:=-1;end;15    for j:=1 to tot do16     begin17      k:=i*p[j];18      if k>maxn then break;19      check[k]:=true;20      if i mod p[j]<>0 then mu[k]:=-mu[i]21      else begin mu[k]:=0;break;end;22     end;23    end;24  for i:=1 to maxn do sum[i]:=sum[i-1]+mu[i];25  end;26 function f(x,y:longint):int64;27  var i,last,t:longint;28  begin29  x:=x div w;y:=y div w;30  f:=0;31  if x>y then begin t:=x;x:=y;y:=t;end;32  i:=1;33  while i<=x do34   begin35    last:=min(x div (x div i),y div (y div i));36    inc(f,(sum[last]-sum[i-1])*(x div i)*(y div i));37    i:=last+1;38   end;39  exit(f);40  end;41 procedure main;42  begin43  get;44  readln(n);45  for i:=1 to n do46   begin47    readln(a,b,c,d,w);48    ans:=0;49    inc(ans,f(b,d));50    dec(ans,f(a-1,d));51    dec(ans,f(b,c-1));52    inc(ans,f(a-1,c-1));53    writeln(ans);54   end;55  end;56 begin57  main;58 end.59