#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100005;
namespace Fenwick {
	int c[N];
	void add(int x, int val) {
		while (x < N) {
			c[x] += val;
			x += x & (-x);
		}
	}
	int query(int x) {
		int ans = 0;
		while (x > 0) {
			ans += c[x];
			x -= x & (-x);
		}
		return ans;
	}
}
struct Value {
	int sigma_1, i;
} value[N];
bool operator < (const Value & a, const Value & b) {
	return a.sigma_1 < b.sigma_1;
}
bool is_prime[N];
int prime[N], pcnt;
int mu[N], g[N];
void pre() {
	for (int i = 2; i < N; i++) {
		is_prime[i] = true;
	}
	value[1].sigma_1 = 1;
	mu[1] = 1;
	for (int i = 2; i < N; i++) {
		if (is_prime[i]) {
			pcnt++;
			prime[pcnt] = i;
			mu[i] = -1;
			g[i] = i + 1;
			value[i].sigma_1 = i + 1;
		}
		for (int j = 1; i * prime[j] < N && j <= pcnt; j++) {
			is_prime[i * prime[j]] = false;
			if (i % prime[j] != 0) {
				mu[i * prime[j]] = -mu[i];
				g[i * prime[j]] = prime[j] + 1;
				value[i * prime[j]].sigma_1 = value[i].sigma_1 * (prime[j] + 1);
			} else {
				mu[i * prime[j]] = 0;
				g[i * prime[j]] = g[i] * prime[j] + 1;
				value[i * prime[j]].sigma_1 = value[i].sigma_1 / g[i] * g[i * prime[j]];
				break;
			}
		}
	}
	for (int i = 1; i < N; i++) {
		value[i].i = i;
	}
	sort(value + 1, value + N);
}
struct Query {
	int n, m, a, id;
} query[N];
bool operator < (const Query & a, const Query & b) {
	return a.a < b.a;
}
int ans[N];
int min(int a, int b) {
	return a < b ? a : b;
}
int solve(int n, int m) {
	if (n > m) {
		n ^= m ^= n ^= m;
	}
	int ans = 0;
	for (int l = 1, r; l <= n; ) {
		r = min(n / (n / l), m / (m / l));
		ans += (Fenwick::query(r) - Fenwick::query(l - 1)) * (n / l) * (m / l);
		l = r + 1;
	}
	return ans;
}
int main() {
	pre();
	int q;
	scanf("%d", &q);
	for (int i = 1; i <= q; i++) {
		scanf("%d %d %d", &query[i].n, &query[i].m, &query[i].a);
		query[i].id = i;
	}
	sort(query + 1, query + q + 1);
	for (int i = 1, j = 1; i <= q; i++) {
		while (j < N && value[j].sigma_1 <= query[i].a) {
			for (int k = value[j].i; k < N; k += value[j].i) {
				Fenwick::add(k, value[j].sigma_1 * mu[k / value[j].i]);
			}
			j++;
		}
		ans[i] = solve(query[i].n, query[i].m);
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i] & 2147483647);
	}
	return 0;
}