rt 测评记录

#include<bits/stdc++.h>
#define MAXN 50005
#define ll long long
using namespace std;

inline int read(){
    int x=0;
    int f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
    	if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}

int T;
int k;
int mu[MAXN],sum[MAXN];
int pm[MAXN],cnt;
bool ntp[MAXN];
int ans;

void get_mu(){
	int n=50000;
	mu[1]=1;
	for(int i=2;i<=n;i++){
		if(!ntp[i]){
			pm[++cnt]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=cnt&&pm[j]*i<=n;j++){
			int t=pm[j]*i;
			ntp[t]=1;
			if(i%pm[j]==0){
				mu[t]=0;
				break;
			}
			mu[t]-=mu[i];
		}
	}
	for(int i=1;i<=n;i++){
		sum[i]=(sum[i-1]+mu[i]);
	}
}

int calc(int n,int m){
	int res=0;
	int i,j;
	for(i=1;i<=min(n,m);i++){
		j=min(n/(n/i),m/(m/i));
		res=(res+(sum[j]-sum[i-1])*(n/(i*k))*(m/(i*k)));
	}
	return res;
}

int main(){
	T=read();
	get_mu();
	int a,b,c,d;
	while(T--){
		a=read();b=read();c=read();d=read();
		k=read();
		int ans=calc(b,d)-calc(a-1,d)-calc(b,c-1)+calc(a-1,c-1);
		printf("%lld\n",ans);
	}
	return 0;
}