#include<map>

#include<set>

#include<ctime>

#include<cmath>

#include<stack>

#include<queue>

#include<string>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define lowbit(x) (x & (-x))

#define INOPEM freopen("in.txt", "r", stdin)

#define OUTOPEN freopen("out.txt", "w", stdout)

typedef unsigned long long int ull;

typedef long long int ll;

const double pi = 4.0*atan(1.0);

const int inf = 0x3f3f3f3f;

const int maxn = 1e5+;

const int maxm = 1e9+;

const int mod = 1e9+;

using namespace std;

int n, m;

int T, tol;

bool pri[maxn];

vector<int> vec[maxn];

void handle() {

    memset(pri, true, sizeof pri);

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

        if(pri[i]) {

            vec[i].push_back(i);

            for(int j=; i*j<maxn; j++) {

                vec[i*j].push_back(i);

                pri[i*j] = false;

            }

        }

    }

}

ll solve(ll x, int k) {

    ll ans = ;

    int len = vec[k].size();

    for(int i=; i<(<<len); i++) {

        int cnt = ;

        ll tmp = ;

        for(int j=; j<len; j++) {

            if(i & (<<j)) {

                cnt++;

                tmp *= vec[k][j];

            }

        }

        if(cnt & )    ans += x / tmp;

        else        ans -= x / tmp;

    }

    return ans;

}

int main() {

    handle();

    int cas = ;

    int T;

    scanf("%d", &T);

    while(T--) {

        int a, b, k;

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

        if(k == ) {

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

            continue;

        }

        n /= k, m /= k, k = ;

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

        ll ans = ;

        //[i, m]

        for(int i=; i<=n; i++) {

            ans += 1ll * (m-i+) - 1ll * (solve(m, i) - solve(1ll * (i-), i));

        }

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

    }

    return ;

}