#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn=1e6;

int prime[maxn+];

bool check[maxn+];

int mu[maxn+];

void init()

{

    mu[]=;

    int tot=;

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

    {

        if(!check[i])

        {

            prime[tot++]=i;

            mu[i]=-;

        }

        for(int j=;j<tot;j++)

        {

            if(i*prime[j]>maxn) break;

            check[i*prime[j]]=true;

            if(i%prime[j]==)

            {

                mu[i*prime[j]]=;

                break;

            }

            else

            {

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

            }

        }

    }

}

int main()

{

    int T;

    int a,b,c,d,k;

    init();

    scanf("%d",&T);

    for(int kase=;kase<=T;kase++)

    {

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

        if(k==)

        {

             printf("Case %d: 0\n",kase);

             continue;

        }

        b/=k;

        d/=k;

        if(b>d) swap(b,d);

        LL ans=;

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

            ans+=(LL)mu[i]*(b/i)*(d/i);

        LL t=;

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

            t+=(LL)mu[i]*(b/i)*(b/i);

        ans-=t/;

        printf("Case %d: %I64d\n",kase,ans);

    }

}