#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 50000
int pr,p[N+10],mu[N+10];
bool v[N+10];
void init(){
	memset(v,0,sizeof(v));
	pr=0;mu[0]=0;mu[1]=1;
	for(int i=2;i<=N;i++){
		if(!v[i])p[++pr]=i,mu[i]=-1,v[i]=1;
		for(int j=1;j<=pr&&i*p[j]<=N;j++){
			v[i*p[j]]=1;
			if(i%p[j]==0){
				mu[i*p[j]]=0;
				break;
			}
			mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=1;i<=N;i++)mu[i]+=mu[i-1];
}
int calc(int n,int m){
	if(n>m)swap(n,m);
	int ans=0;
	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;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	init();
	int t;cin>>t;
	while(t--){
		int a,b,c,d,k;cin>>a>>b>>c>>d>>k;a--,c--;a/=k,b/=k,c/=k,d/=k;
		cout<<calc(b,d)-calc(a,d)-calc(b,c)+calc(a,c)<<'\n';
	}
	
	return 0;
}

洛谷同题