#include<bits/stdc++.h>
#define ll long long
#define R register int
using namespace std;
const int maxn=50010;
ll n,a,b,c,d,k,num=0,ans,s[maxn]={0},p[maxn]={0},vis[maxn]={0},mb[maxn]={0};
ll work(ll x,ll y,ll z)//一些数论分块 
{  ll limits=min(x/z,y/z),ret=0;
   for(R l=1,r=0;l<=limits;l=r+1)
   {  r=min((x/(x/l)),(y/(y/l)));
      ret+=((1ll*x/(1ll*z*l))*(1ll*y/(1ll*z*l)))*(s[r]-s[l-1]);
   }
   return ret;
}
inline void read(ll &x)
{  ll e=0,w=1;
   char ch=getchar();
   while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
   while(isdigit(ch)) {e=(e<<1)+(e<<3)+ch-48;ch=getchar();}
   x=e*w;
}
int main()
{   read(n);
    mb[1]=1;
    for(R i=2;i<=50000;++i)
    {  if(!vis[i])
       {  mb[i]=-1;
          p[++num]=i;
	   }
	   for(R j=1;i*p[j]<=50000&&j<=num;j++)
	   {  vis[i*p[j]]=1;
	      if(i%p[j]==0)
	         break;
		  //cout<<p[j]<<endl;
		  mb[i*p[j]]=-mb[i];
	   }
	}//预处理莫比乌斯函数前缀和 
	for(R i=1;i<=50000;++i)
	  s[i]=s[i-1]+mb[i];
    while(n--)
    {  read(a);
       read(b);
       read(c);
       read(d);
       read(k);
       ans=work(b,d,k)-work(b,c-1,k)-work(a-1,d,k)+work(a-1,c-1,k);//容斥原理 
       printf("%lld\n",ans);
	}
	return 0;
}

为什么会TLE7个点？ 求助！！！！谢谢！！！