#include<iostream>

#include<algorithm>

#include<set>

#include<vector>

#include<queue>

#include<cstdlib>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

const int N=1e5+;

int T,prime[N],mu[N],n,m;

bool vis[N];

void getmu()

{

    mu[] = ;

    int cnt = ;

    for(int i=; i<=N-; i++)

    {

        if(!vis[i])

        {

            prime[cnt++] = i;

            mu[i] = -;

        }

        for(int j=; j<cnt&&i*prime[j]<=N-; j++)

        {

            vis[i*prime[j]] = ;

            if(i%prime[j]) mu[i*prime[j]] = -mu[i];

            else

            {

                mu[i*prime[j]] = ;

                break;

            }

        }

    }

}

LL F(LL x){

   LL y=m/x;

   x=n/x;

   y-=x;

   return x*(x-)/+x+y*x;

}

int main(){

    getmu();

    scanf("%d",&T);

    int cas=;

    while(T--){

      int k;

      scanf("%d%d%d%d%d",&n,&n,&m,&m,&k);

      if(n>m)swap(n,m);

      printf("Case %d: ",++cas);

      if(!k){

        printf("0\n");

        continue;

      }

      LL ans=;

      int mx=min(n,m);

      for(int i=k;i<=mx;i+=k){

         ans+=mu[i/k]*F(i);

      }

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

    }

    return ;

}