HAOI2011 problem b

 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  begin
10  fillchar(check,sizeof(check),false);
11  tot:=0;mu[1]:=1;
12  for i:=2 to maxn do
13   begin
14    if not(check[i]) then begin inc(tot);p[tot]:=i;mu[i]:=-1;end;
15    for j:=1 to tot do
16     begin
17      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  begin
29  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 do
34   begin
35    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  begin
43  get;
44  readln(n);
45  for i:=1 to n do
46   begin
47    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 begin
57  main;
58 end.
59