/**************************************************************

     Problem: 2301

     User: Tunix

     Language: C++

     Result: Accepted

     Time:10964 ms

     Memory:2932 kb

 ****************************************************************/

 //BZOJ 2301

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}

     return v*=sign;

 }

 /*******************tamplate********************/

 const int N=;

 typedef long long LL;

 int prime[N],mu[N];

 bool check[N];

 LL sum[N];

 void getmu(int n){

     memset(check,,sizeof check);

     mu[]=;

     int tot=;

     F(i,,n){

         if(!check[i]){

             prime[tot++]=i;

             mu[i]=-;

         }

         rep(j,tot){

             if(i*prime[j]>n)break;

             check[i*prime[j]]=;

             if(i%prime[j]==){

                 mu[i*prime[j]]=;

                 break;

             }

             else mu[i*prime[j]]=-mu[i];

         }

     }

     F(i,,n) sum[i]=sum[i-]+mu[i];

 }

 LL calc(int m,int n,int k){

     int i,last;

     LL re=;

     n/=k; m/=k;

     for(i=;i<=m && i<=n;i=last+){

         last=min(n/(n/i),m/(m/i));

         re+=(sum[last]-sum[i-])*(m/i)*(n/i);

     }

     return re;

 }

 int main(){

     getmu(N);

     int T=getint();

     while(T--){

         int a=getint(), b=getint(), c=getint(), d=getint(), k=getint();

         printf("%lld\n", calc(b,d,k)-calc(a-,d,k)-calc(b,c-,k)+calc(a-,c-,k));

     }

     return ;

 }