Description
对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。
Input
第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k
Output
共n行，每行一个整数表示满足要求的数对(x,y)的个数
Sample Input
2
2 5 1 5 1
1 5 1 5 2
Sample Output
14
3
HINT
100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000
生病了……智商急速下降……
盯了会屏幕，发现头晕不想写……反正差不多……跟后面一起写吧……
program bzoj2301;
const
maxn=50000;
var
n,a,b,c,d,k,i,j:longint;
f,p:array [0..maxn] of longint;
procedure swap (var a,b:longint);inline;
begin
if a=b then exit;
a:=a xor b;
b:=a xor b;
a:=a xor b;
end;
function calc (a,b:longint):int64;
var
i,j,k:longint;
ans:int64;
begin
ans:=0;
if a>b then swap (a,b);
if a=0 then exit(0);
i:=1;
while i<=a do
begin
if a div (a div i)<b div (b div i) then k:=a div (a div i)
else k:=b div (b div i);
ans:=ans+(p[k]-p[i-1])*int64(a div i)*(b div i);
i:=k+1;
end;
exit(ans);
end;
begin
for i:=2 to maxn do
if f[i]=0 then
for j:=i to maxn div i do
f[i*j]:=i;
p[1]:=1;
for i:=2 to maxn do
if f[i]=0 then p[i]:=-1
else
if i div f[i] mod f[i] = 0 then p[i]:=0
else p[i]:=-p[i div f[i]];
for i:=2 to maxn do
p[i]:=p[i]+p[i-1];
read(n);
while n>0 do
begin
dec(n);
read(a,b,c,d,k);
writeln(calc(b div k,d div k)-calc((a-1) div k,d div k)-calc(b div k,(c-1) div k)+calc((a-1) div k,(c-1) div k));
end;
end.