莫比烏斯函數
\(\mu(n) = \begin{cases} 1, n = 1 \\ (-1)^k,n = \prod_{i = 1}^k p_i 且 p_i 互質 \\ 0,else \end{cases}\)

性質：
1.對于任意正整數 \(n\)，\(\sum_{d|n}\mu(d) = [n = 1]\)
2.對于任意正整數 \(n\)，\(\sum_{d|n} \frac{\mu(d)}w0obha2h00 = \frac{\phi(n)}{n}\)

莫比烏斯反演
定義：\(F(n)\) 和 \(f(n)\) 是定義在非負整數集合上的兩個函數，并且滿足 \(F(n) = \sum_{d|n}f(d)\)，可得 \(f(n) = \sum_{d|n}\mu(d)F(\lfloor \frac{n}w0obha2h00 \rfloor)\)

例：https://www.luogu.com.cn/problem/P3455

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5e4 + 10;
bool st[N];
int mu[N], prime[N], cnt, sum[N];
void getMu(){
	mu[1] = 1;
	for (int i = 2; i <= N - 10; i ++ ){
		if (!st[i]){
			prime[ ++ cnt] = i;
			mu[i] = -1;
		}
		for (int j = 1; j <= cnt && i * prime[j] <= N - 10; j ++ ){
			st[i * prime[j]] = true;
			if (i % prime[j] == 0){
				mu[i * prime[j]] = 0;
				break;
			}
			mu[i * prime[j]] = -mu[i];
		}
	}
	for (int i = 1; i <= N - 10; i ++ ){
		sum[i] = sum[i - 1] + mu[i];
	}
}
void solve(){
	int n, m, k;
	cin >> n >> m >> k;
	n = n / k;
	m = m / k;
	if (n < m){
		swap(n, m);
	}
	LL ans = 0;
	for (int i = 1, j = 0; i <= m; i = j + 1){
		j = min(n / (n / i), m / (m / i));
		ans += (LL)(sum[j] - sum[i - 1]) * (n / i) * (m / i);
	}
	cout << ans << "\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	getMu();
	int T;
	cin >> T;
	while (T -- ){
		solve();
	}
	return 0;
}