#23WA | #456789 10 TLE

#include<bits/stdc++.h>
#define MAXN 50005
#define int 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;
}

signed 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;
}