#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define ll long long
#define N 100000

int tot;
int prime[N+10];
bool isprime[N+10];
int phi[N+10];
void prime_pri()
{
    tot=0;
    phi[1]=1;
    memset(isprime,true,sizeof(isprime));
    isprime[0]=isprime[1]=false;
    for(int i=2;i<=N;i++)
    {
        if(isprime[i])
        {
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot;j++)
        {
            if(i*prime[j]>N) break;
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
            {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}
int fatcnt;
int factor[N][2];
int getfactors(int x)
{
    fatcnt=0;
    int tmp=x;
    for(int i=0;prime[i]<=tmp/prime[i];i++)
    {
        factor[fatcnt][1]=0;
        if(tmp%prime[i]==0)
        {
            factor[fatcnt][0]=prime[i];
            while(tmp%prime[i]==0)
            {
                factor[fatcnt][1]++;
                tmp/=prime[i];
            }
            fatcnt++;
        }
    }
    if(tmp!=1)
    {
        factor[fatcnt][0]=tmp;
        factor[fatcnt++][1]=1;
    }
    return fatcnt;
}
int cal(int n,int m) //求1到n中与m互质的数的个数
{
    int tmp,cnt,ans=0;
    getfactors(m);
    for(int i=1;i<(1<<fatcnt);i++) //0表示不选择因子
    {
        cnt=0;
        tmp=1;
        for(int j=0;j<fatcnt;j++)
        {
            if(i&(1<<j))
            {
                cnt++;
                tmp*=factor[j][0];
            }
        }
        if(cnt&1) ans+=n/tmp;
        else ans-=n/tmp;
    }
    return n-ans;
}
int main()
{
    prime_pri();
    int T,iCase=1;
    int a,b,k;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d%d",&a,&a,&b,&b,&k);
        if(k==0) //除0特判
        {
            printf("Case %d: 0\n",iCase++);
            continue;
        }
        a/=k,b/=k;
        if(a>b) swap(a,b);
        ll ans=0;
        for(int i=1;i<=b;i++)
        {
            if(i<=a) ans+=phi[i];
            else ans+=cal(a,i);
        }
        printf("Case %d: %lld\n",iCase++,ans);
    }
    return 0;
}