设$f(d)=\sum_{i=1}^N\sum_{j=1}^M[gcd(i,j)==d],\\F(n)=\sum_{n|d}f(d)=\lfloor \frac{N}{n} \rfloor \lfloor \frac{M}{n} \rfloor$
则$f(n)$
$=\sum_{n|d}\mu(\frac{n}{d})F(d)$
$=\sum_{n|d}\mu(\frac{n}{d})\lfloor \frac{N}{d} \rfloor \lfloor \frac{M}{d} \rfloor$
设$d=kn$
$=\sum_{k=1}^{min(\lfloor \frac{N}{n} \rfloor,\lfloor \frac{M}{n} \rfloor)}\space\mu(k)\lfloor \frac{N}{kn} \rfloor \lfloor \frac{M}{kn} \rfloor$
所以对$\lfloor \frac{N}{kn} \rfloor \lfloor \frac{M}{kn} \rfloor$整除分块，对$\mu(k)$搞一个前缀和。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define R register ll
using namespace std;
namespace Fread {
static char B[<<],*S=B,*D=B;
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
}using Fread::g;
int n,a,b,c,d,x,cnt;
int mu[],pri[];
bool v[];
inline void MU(int n) { mu[]=;
for(R i=;i<=n;++i) {
if(!v[i]) pri[++cnt]=i,mu[i]=-;
for(R j=;j<=cnt&&i*pri[j]<=n;++j) {
v[i*pri[j]]=true;
if(i%pri[j]==) break;
mu[i*pri[j]]=-mu[i];
}
} for(R i=;i<=n;++i) mu[i]+=mu[i-];
}
inline ll calc(int a,int b) { R ret=; a>b?swap(a,b):void();
for(R l=,r;l<=a;l=r+) {
r=min(a/(a/l),b/(b/l));
ret+=(ll)(mu[r]-mu[l-])*(a/l)*(b/l);
} return ret;
}
signed main() {
#ifdef JACK
freopen("NOIPAK++.in","r",stdin);
#endif
MU(); n=g(); while(n--) { R ans=;
a=g()-,b=g(),c=g()-,d=g(),x=g();
printf("%lld\n",calc(b/x,d/x)-calc(a/x,d/x)-calc(b/x,c/x)+calc(a/x,c/x));
}
}
2019.06.09