题链：
http://www.lydsy.com/JudgeOnline/problem.php?id=2301
题解：
莫比乌斯反演,入门题。
只是多了一个下界，(另外本题把(a,b)和(b,a)看成两种不同的答案)
把问题拆成四个就好了。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 100500
using namespace std;
int mu[MAXN],pmu[MAXN];
void Mobius_Sieve(){
static bool np[MAXN]; mu[1]=1; pmu[1]=1;
static int prime[MAXN],pnt;
for(int i=2;i<=100000;i++){
if(!np[i]) prime[++pnt]=i,mu[i]=-1;
pmu[i]=pmu[i-1]+mu[i];
for(int j=1;j<=pnt&&i<=100000/prime[j];j++){
np[prime[j]*i]=1;
if(i%prime[j]) mu[i*prime[j]]=-mu[i];
else mu[i*prime[j]]=0;
if(i%prime[j]==0) break;
}
}
}
long long work(int n,int m){
long long ret=0,tmp;
for(int i=1,last;i<=min(n,m);i=last+1){
last=min(n/(n/i),m/(m/i));
tmp=1ll*(pmu[last]-pmu[i-1])*(n/i)*(m/i);
ret+=tmp;
}
return ret;
}
long long ans(int n,int m,int k){
return work(n/k,m/k)/*-work(min(n,m)/k,min(n,m)/k)/2*/;
}
int main(){
Mobius_Sieve();
int a,b,c,d,k,Case; long long ANS;
scanf("%d",&Case);
for(int i=1;i<=Case;i++){
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
if(k==0){printf("0\n"); continue;}
//printf("%lld\n",ans(b,d,k));
ANS=ans(b,d,k)-ans(a-1,d,k)-ans(b,c-1,k)+ans(a-1,c-1,k);
/*
int dn=max(a,c),up=min(b,d);
long long _ANS=ans(up,up,k)-ans(dn-1,up,k)-ans(up,dn-1,k)+ans(dn-1,dn-1,k);
printf("不重复:%lld\n",ANS-_ANS/2);
*/
printf("%lld\n",ANS);
}
return 0;
}