#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define N 60000#define M 50000int mindiv[N];int zhi[N];int zhin;int u[N];void shai(int x){   for(int i=1;i<=x;i++)mindiv[i]=i;   u[1]=1;   for(int i=2;i<=x;i++){       if(mindiv[i]==i)zhi[++zhin]=i,u[i]=-1;       for(int j=1;j<=zhin&&zhi[j]<=mindiv[i]&&zhi[j]*i<=x;j++){            mindiv[i*zhi[j]]=zhi[j];            if(zhi[j]==mindiv[i])u[i*zhi[j]]=0;            else u[i*zhi[j]]=-u[i];        }        }    }int s[N];int gcds(int a,int b,int k){    if(a==0||b==0)return 0;    int l,r=0;    a/=k;    b/=k;    int ans=0;    int lim=min(a,b);    for(;;){        l=r+1;        if(l>lim)break;        r=min((a/(a/l)),b/(b/l));        ans+=(a/l)*(b/l)*(s[r]-s[l-1]);    }        return ans;}int main(){    shai(M);    for(int i=1;i<=M;i++)s[i]=s[i-1]+u[i];    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++){       int a,b,c,d,k;       scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);       printf("%d\n",gcds(b,d,k)-gcds(b,c-1,k)-gcds(a-1,d,k)+gcds(a-1,c-1,k));        }    }