#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define repi(i, a, b) for(int i=(a); i>(b); i--)
#define db(x) (cerr << #x << ": " << (x) << '\n')
#define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
#define tests(t) int t; cin >> t; while(t--)
#define iceil(n, x) (((n) + (x) - 1) / (x))
#define ll long long
#define gcd __gcd
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define sz size()
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)); (v).erase(unique(all(v)), (v).end());
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define pqueue priority_queue
#define si(a) scanf("%d", &a)
#define sll(a) scanf("%lld", &a)
#define bitcount(x) __builtin_popcount(x)
#define cps CLOCKS_PER_SEC
#define PI acos(-1.0l)
#define EPS 1e-6
#define mod 1000000007
#define MOD 1000000007
#define N 100005
using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

template<typename T>
using maxpq = priority_queue<T>;

//All indexing is 0-based
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update> ordered_set;
//methods: find_by_order(k); & order_of_key(k);
//To make it an ordered_multiset, use pairs of (value, time_of_insertion)
//to distinguish values which are similar.

template<class key, class value, class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
//ordered_map<int, int> my_map;


//Returns no. of values x for which ceil(n / x) == y (y must be > 1).
inline ll CC(ll n, ll y) { return iceil(n, y-1) - iceil(n, y); }

//Returns no. of values x for which floor(n / x) == y
inline ll FF(ll n, ll y) { return n / y - n / (y+1); }

//a and b are assumed to be taken modulo p
inline int add(int a, int b, int p = mod){ int c = a + b; if(c >= p) c -= p; return c;}
inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c;}
inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p;}

#define int ll
//#define trace(...) 42

//Links: 
//Linear sieve and Multiplicative functions: https://c...content-available-to-author-only...s.com/blog/entry/54090
//Mobius Inversion:                          https://c...content-available-to-author-only...s.com/blog/entry/53925

/* Logic used: Every composite no. can be uniquely represented as 
    q = i * p; where p is the smallest prime factor and i >= p.
    We just need to ensure that every composite no. gets marked exactly once
    and we do that when we reach i by considering all primes p <= i
    and marking the corresponding nos. (i * p) as composites.
*/

int M[N], cnt[N];
bool isPrime[N];
vector<int> primes;

//Computes the list of all prime numbers <= n and stores in prime.
//Also computes the value of the multiplicative function, func(i) for all i from 1 to n
//and stores in f[i].
void sieve(int n) {
    fill(isPrime, isPrime+n+1, 1);
    primes.clear();

    M[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(isPrime[i]) {
            primes.push_back(i);
            M[i] = -1; cnt[i] = 1;
        }
        for(int p : primes) {
            if(i * 1ll * p > n) break;
            isPrime[i*p] = 0;
            if(i % p == 0) {
                M[i*p] = 0; //Since p^2 divides i
                cnt[i*p] = cnt[i] + 1;
                break;
                //if p divides i then for all primes q > p,
                //the spf of i*q would be p and not q.
            }
            else {
                M[i*p] = M[i] * M[p];
                cnt[i*p] = 1;
            }
        }
    }
}

void prep() {
    sieve(N-5);
}

int solve(int b, int d, int k) {
    int m = min(b/k, d/k);
    int ans = 0;

    for(int l = 1; l <= m; l++) {
        ans += M[l] * (b/k/l) * (d/k/l);
    }
    return ans;
}

int32_t main()
{   
    #ifdef CP
        freopen("/home/tarun/Desktop/input.txt", "r", stdin);
    //  freopen("/home/tarun/Desktop/output.txt", "w", stdout);
    #endif
    sync;
    clock_t clk = clock();
    //cerr << "I will return...\n";
    
    prep();
    
    int oo = 1;
    tests(t) {
        cout << "Case " << oo++ << ": ";
        int a, b, c, d, k; cin >> a >> b >> c >> d >> k;
        int m = min(b, d);
        if(k == 0 || m < k) {
            cout << 0 << '\n'; continue;
        }

        int X = solve(b, d, k);
        int Y = solve(m, m, k);

        int ans = X - (Y-1)/2;

        //trace(X, Y);

        cout << ans << '\n';
    }

    //cerr << "...don't you ever hang your head.\n";
    //cerr << "Time (in ms): " << double(clock() - clk) * 1000.0 / cps << '\n';
}

//Compile using:
//g++ -o filename.exe --std=c++11 filename.cpp
//Use -D CP for defining a macro CP in the local environment