P3455

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5e4 + 10;

int T, mu[N], prim[N], cnt;
bool vis[N];

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

signed main() {
//	freopen("P3455_1.in","r",stdin);
//	freopen("P3455.out","w",stdout);
	cin >> T;
	miu(N);
	while (T--) {
		int ans = 0, n, m, k, l, r = 0;
		cin >> n >> m >> k;
		n = n / k, m = m / k;
		if (n < m) swap(n, m);
		for (l = 1; l <= m; l = r + 1) {
			r = min(n / (n / l), m / (m / l));
			ans += (mu[r] - mu[l - 1]) * (long long) (n / l) * (m / l);
		}
		cout << ans << endl;
	}
//	system("fc P3455.out P3455_1.out");
	return 0;
}

acwing上过了，luogu上0分