/***

 对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数

 **/

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 int isprime[maxn],prime[maxn],mu[maxn],sum[maxn];

 int t,a,b,c,d,k;

 int cnt;

 void mobius(int n){

     int i,j;

     cnt =;

     mu[] =;

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

         if(!isprime[i]){

             prime[cnt++] = i;

             mu[i] = -;

         }

         for(j=;j<cnt&&i*prime[j]<=n;j++){

             isprime[i*prime[j]] = ;

             if(i%prime[j])

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

             else{

                 mu[i*prime[j]] = ;

                 break;

             }

         }

     }

 }

 long long solve(int n,int m){

     int i,la;

     long long ret =;

     if(n>m)

         swap(n,m);

     for(i=,la=;i<=n;i=la+){

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

         ret += (long long )(sum[la]-sum[i-])*(n/i)*(m/i);

     }

     return ret;

 }

 int main(){

     int i,j;

     mobius();

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

         sum[i] = sum[i-]+mu[i];

     scanf("%d",&t);

     while(t--){

         scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);

         long long ans;

         ans = solve(b/k,d/k)-solve((a-)/k,d/k)

             -solve((c-)/k,b/k)+solve((a-)/k,(c-)/k);

         printf("%lld\n",ans);

     }

     return ;

 }