rt。把 #define int long long 取消注释。

全开 long long

不全开 long long

#include <bits/stdc++.h> //https://www.luogu.com.cn/article/e8des884
//#define int long long
using namespace std;

const int maxn = 50010;

bool vis[maxn];
int prim[maxn], miu[maxn], sum[maxn], cnt;
long long k;

void get_miu(int n) {
	miu[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			miu[i] = -1;
			prim[++cnt] = i;
		}
		for (int j = 1; j <= cnt && i * prim[j] <= n; j++) {
			vis[i * prim[j]] = 1;
			if (i % prim[j] == 0) break;
			else miu[i * prim[j]] = -miu[i];
		}
	}
	for (int i = 1; i <= n; i++) sum[i] = sum[i-1] + miu[i];
}

long long calc(int a, int b) { //分块 
	int max_rep = min(a, b);
	long long ans = 0;
	for (int l = 1, r; l <= max_rep; l = r + 1) {
		r = min(a / (a/l), b / (b/l));
		ans += (a / (l*k)) * (b / (l*k)) * (sum[r] - sum[l-1]);
	}
	return ans;
}

signed main() {
	cin.tie(0); ios::sync_with_stdio(0);
	int T;
	cin >> T;
	get_miu(50000);
	while (T--) {
		int a, b, c, d;
		cin >> a >> b >> c >> d >> k;
		cout << calc(b, d) - calc(b, c-1) - calc(a-1, d) + calc(a-1, c-1) << "\n";
	}
}