链接https://www.lydsy.com/JudgeOnline/problem.php?id=2301
#include<iostream>
#include<cstring>
#include<string>
#define FO(n) for(int i=1;i<=(n);i++)
#define FOR(i,n) for(int (i)=1;(i)<=(n);(i)++)
#define ll long long
#define maxn 50000
using namespace std;
ll mu[maxn+5];
int a,b,c,d,k,n,m;
void get_mu(){//利用欧拉筛推出mu数组
int isp[maxn+5],prime[maxn+5];
memset(isp,1,sizeof(isp));
prime[0]=0,isp[1]=0,mu[1]=1;
for(int i=2;i<=maxn;i++){
if(isp[i]){
mu[i]=-1;
prime[++prime[0]]=i;
}
for(int j=1;j<=prime[0]&&i*prime[j]<=maxn;j++){
isp[i*prime[j]]=0;
if(!(i%prime[j])){
mu[i*prime[j]]=0;
break;
}
else{
mu[i*prime[j]]=-mu[i];
}
}
mu[i]+=mu[i-1];
}
}
ll cal(int x,int y){//分块
if(x>y)swap(x,y);
ll ans=0;
for(int i=1,last;i<=x;i=last+1){
last=min(x/(x/i),y/(y/i));
ans+=(ll)(mu[last]-mu[i-1])*(x/i)*(y/i);
}
return ans;
}
int main(){
int t;
get_mu();
cin>>t;
while (t--)
{
cin>>a>>b>>c>>d>>k;
cout<<
cal(b/k, d/k)-cal(b/k, (c-1)/k)-cal((a-1)/k, d/k)+cal((a-1)/k, (c-1)/k)
<<"\n";
}
}
