传送门:
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define re register
const int N=5e4+10;
const int M=5e4;
inline void read(int &a)
{
a=0;
int d=1;
char ch;
while(ch=getchar(),ch>'9'||ch<'0')
if(ch=='-')
d=-1;
a=ch^48;
while(ch=getchar(),ch>='0'&&ch<='9')
a=(a<<3)+(a<<1)+(ch^48);
a*=d;
}
int pri[N],cnt;
ll mu[N];
bool vis[N];
inline void init()
{
mu[1]=1;
for(re int i=2;i<=M;i++)
{
if(!vis[i])
pri[++cnt]=i,mu[i]=-1;
for(re int j=1;j<=cnt&&i*pri[j]<=M;j++)
{
vis[i*pri[j]]=1;
if(i%pri[j]==0)
break;
mu[i*pri[j]]=-mu[i];
}
}
for(re int i=1;i<=M;i++)
mu[i]+=mu[i-1];
}
ll solve(int n,int m,int k)
{
ll ans=0;
if(n>m)
swap(n,m);
n/=k;
m/=k;
for(int l=1,r;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans+=(mu[r]-mu[l-1])*(n/l)*(m/l);
}
return ans;
}
int main()
{
init();
int T;
read(T);
while(T--)
{
int a,b,c,d,k;
read(a);
read(b);
read(c);
read(d);
read(k);
if(k==0)
{
printf("0
");
continue;
}
printf("%lld
",solve(b,d,k)-solve(b,c-1,k)-solve(a-1,d,k)+solve(a-1,c-1,k));
}
return 0;
}