#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)const int N=50005;int p[N], np[N], cnt, mu[N];ll sum[N];void init() {	mu[1]=1;	for2(i, 2, N) {		if(!np[i]) p[++cnt]=i, mu[i]=-1;		for1(j, 1, cnt) {			int t=p[j]*i; if(t>=N) break;			np[t]=1;			if(i%p[j]==0) { mu[t]=0; break; }			mu[t]=-mu[i];		}	}	for2(i, 1, N) sum[i]=sum[i-1]+mu[i];}inline ll cal(int a, int b, int c, int d, int k) {	return max(0ll, (ll)((b/k)-((a-1)/k))*(ll)((d/k)-((c-1)/k))); }int main() {	init();	int n=getint();	while(n--) {		int a=getint(), b=getint(), c=getint(), d=getint(), k=getint();		a=(a+k-1)/k; b/=k; c=(c+k-1)/k; d/=k;		//dbg(a); dbg(b); dbg(c); dbg(d);		int len=min(b, d);		ll ans=0;		int pos;		for(int i=1; i<=len; i=pos+1) {			pos=min(b/(b/i), d/(d/i));			if((a-1)/i!=0) pos=min(pos, (a-1)/((a-1)/i));			if((c-1)/i!=0) pos=min(pos, (c-1)/((c-1)/i));			ans+=(sum[pos]-sum[i-1])*cal(a, b, c, d, i);		}		printf("%lld\n", ans);	}	return 0;}

第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k

共n行，每行一个整数表示满足要求的数对(x,y)的个数

100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000