#include<algorithm>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 int mul[],p[],mark[],sum[];

 int read(){

     char ch=getchar();int t=,f=;

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

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

     return t*f;

 }

 void init(){

     mul[]=;

     for (int i=;i<=;i++){

         if (!mark[i]){

             p[++p[]]=i;

             mul[i]=-;

         }

         for (int j=;j<=p[]&&p[j]*i<=;j++){

             mark[i*p[j]]=;

             if (i%p[j]) mul[p[j]*i]=mul[i]*(-);

             else{

                 mul[p[j]*i]=;

                 break;

             }

         }

     }

     sum[]=;

     for (int i=;i<=;i++) sum[i]=sum[i-]+mul[i];

 }

 int cal(int a,int b){

     if (a>b) std::swap(a,b);

     int res=;

     for (int i=,j;i<=a;i=j+){

         j=std::min(a/(a/i),b/(b/i));

         res+=(a/i)*(b/i)*(sum[j]-sum[i-]);

     }

     return res;

 }

 int main(){

     int T=read();

     init();

     while (T--){

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

         a--;c--;

         printf("%d\n",std::max(,cal(b/k,d/k)+cal(a/k,c/k)-cal(b/k,c/k)-cal(a/k,d/k)));

     }

 }