#include <bits/stdc++.h>

using namespace std;
const int N=20000;
bool vis[N+10];
int tot,prime[N+10],sum[N+10],mu[N+10];

void Mu(int n)
{
    mu[1]=1;
    for (int i=2; i<=n; i++)
    {
        if (!vis[i])
        {
            prime[++tot]=i;
            mu[i]=-1;
        }
        for (int j=1; j<=tot&&prime[j]*i<=n; j++)
        {
            vis[prime[j]*i]=1;
            if (i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            mu[prime[j]*i]=-mu[i];
        }
    }
    for (int i=1; i<=n; i++)
    {
        sum[i]=sum[i-1]+mu[i];
    }
}
int ans(int n,int m)
{
    if (n>m)
    {
        swap(n,m);
    }
    int last,ret=0;
    for (int i=1; i<=n; i=last+1)
    {
        last=min(n/(n/i),m/(m/i));
        ret+=(n/i)*(m/i)*(sum[last]-sum[i-1]);
    }
    return ret;
}

int main()
{
    Mu(N);
    int _,a,b,c,d,k,ca=0;
    scanf("%d",&_);
    while (_--)
    {
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if (k==0)
        {
            printf("Case %d: 0\n",++ca);
            continue;
        }
        a--;
        c--;
        a/=k;
        b/=k;
        c/=k;
        d/=k;
        int Ans=ans(b,d)-ans(a,d)-ans(b,c)+ans(a,c);
        printf("%d\n",Ans);
    }
}

#include <bits/stdc++.h>

using namespace std;
const int N=200000;
typedef long long ll;
bool vis[N+10];
ll tot,prime[N+10],sum[N+10],mu[N+10];

void Mu(ll n)
{
    mu[1]=1;
    for (ll i=2; i<=n; i++)
    {
        if (!vis[i])
        {
            prime[++tot]=i;
            mu[i]=-1;
        }
        for (ll j=1; j<=tot&&prime[j]*i<=n; j++)
        {
            vis[prime[j]*i]=1;
            if (i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            mu[prime[j]*i]=-mu[i];
        }
    }
    for (ll i=1; i<=n; i++)
    {
        sum[i]=sum[i-1]+mu[i];
    }
}
ll ans(ll n,ll m)
{
    if (n>m)
    {
        swap(n,m);
    }
    ll last,ret=0;
    for (ll i=1; i<=n; i=last+1)
    {
        last=min(n/(n/i),m/(m/i));
        ret+=(n/i)*(m/i)*(sum[last]-sum[i-1]);
    }
    return ret;
}

int main()
{
    Mu(N);
    int _,a,b,c,d,k,ca=0;
    scanf("%d",&_);
    while (_--)
    {
        scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
        if (k==0)
        {
            printf("Case %d: 0\n",++ca);
            continue;
        }
        printf("Case %d: ",++ca);
        ll ans1=0,ans2=0;
        b/=k;
        d/=k;
        for (int i=1; i<=min(b,d); i++)
        {
            ans1+=mu[i]*(b/i)*(d/i);
        }
        for (int i=1; i<=min(b,d); i++)
        {
            ans2+=mu[i]*(min(b,d)/i)*(min(b,d)/i);
        }
        printf("%lld\n",ans1-ans2/2);
    }
}