#include <iostream>
#include <cstring>

using namespace std;

using i64 = long long;

const int N = 50010;

int n, m, primes[N], cnt;
bool st[N];
i64 mu[N];

void init(int n = 50010) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i, mu[i] = -1;
        for (int j = 0; j < cnt && primes[j] * i <= n; j++) {
            st[i * primes[j]] = true;    
            if (i % primes[j] == 0) break;
            mu[i * primes[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= n; i++) mu[i] += mu[i - 1];
}

i64 calc(int n, int m, int k) {
    i64 res = 0;
    n /= k, m /= k;
    if (n > m) swap(n, m);
    for (int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        res += (mu[r] - mu[l - 1]) * (n / l) * (m / l);
    }
    return res;
}

int main() {
    init(50000);
    int T;
    cin >> T;
    while (T--) {
        int a, b, c, d, k;
        cin >> a >> b >> c >> d >> k;
        cout << calc(b, d, k) - calc(a - 1, d, k) - calc(b, c - 1, k) + calc(a - 1, c - 1, k) << '\n';
    }
    return 0;
}