#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#define FILE "read"
using namespace std;
const int MAXN=(int)1e5,D(50);
int cnt,k,check[MAXN+D],mu[MAXN+D],prime[MAXN+D],sum[MAXN+D];
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,f=1; char ch=getc();
		while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();}
		while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();}
		return x*f;
	}
}using namespace INIT;
void pre(){
	mu[1]=1;
	for(int i=2;i<=MAXN;++i){
		if(!check[i])  prime[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&prime[j]*i<=MAXN;++j){
			check[prime[j]*i]=1;
			if(i%prime[j]==0)  {mu[i*prime[j]]=0; break;}
			else mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<=MAXN;++i)  sum[i]=sum[i-1]+mu[i];
}
int solve(int n,int m){
	n/=k;  m/=k; 
	if(n>m) swap(n,m);
	int ans=0,last;
	for(int i=1;i<=n;i=last+1){
		last=min(n/(n/i),m/(m/i));
		ans+=(n/i)*(m/i)*(sum[last]-sum[i-1]);
	}
	return ans;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	int n=read();  pre();
	while(n--){
		int a=read(),b=read(),c=read(),d=read(); k=read();
		printf("%d\n",solve(b,d)-solve(b,c-1)-solve(a-1,d)+solve(a-1,c-1));
	}
	return 0;
}