#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long long LL;
const int maxn = 5e4+5000;
int p[maxn],mo[maxn],phi[maxn],cnt,sum[maxn];
int a,b,c,d,k;
bool vis[maxn];
void init()
{
    mo[1]=1;
    phi[1]=1;
    for(int i=2;i<=maxn-10;i++){
        if(!vis[i]){
            mo[i]=-1;
            phi[i]=i-1;
            p[cnt++]=i;
        }
        for(int j=0;j<cnt&&(ll)i*p[j]<=maxn-10;j++){
            vis[i*p[j]]=true;
            if(i%p[j]==0){
                mo[i*p[j]]=0;
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            mo[i*p[j]]=-mo[i];
            phi[i*p[j]]=phi[i]*(p[j]-1);
        }
    }
}
ll solve (int n,int m)
{
    ll ret =  0;
    if (n>m) swap(n,m);
    for (int i=1,la=0;i<=n;i=la+1){
        la = min(n/(n/i),m/(m/i));
        ret+=(long long)(sum[la]-sum[i-1])*(n/i)*(m/i);
    }
    return ret;
}
int main()
{
    //freopen("de.txt","r",stdin);
    init();
    int T;
    for (int i=1;i<=50000;++i) sum[i] = sum[i-1] + mo[i];
    scanf("%d",&T);
    while (T--){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        ll ans = solve(b/k,d/k)-solve((a-1)/k,d/k)-solve((c-1)/k,b/k)+solve((a-1)/k,(c-1)/k);
        printf("%lld\n",ans);
    }
    return 0;
}