#include<cstdio>

#include<cstring>

#include<algorithm>

#define read(x) x=getint()

using namespace std;

const int N = 1E5;

int getint() {

	int k = 0, fh = 1; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar())

		if (c == '-') fh = -1;

	for(; c >= '0' && c <= '9'; c = getchar())

		k = k * 10 + c - '0';

	return k * fh;

}

bool np[N + 3];

int prime[N + 3], mu[N + 3], f[N + 3], exmin[N + 3], bit[N + 3], up = 0;

void shai() {

	mu[1] = f[1] = 1; int num = 0;

	for(int i = 2; i <= N; ++i) {

		if (!np[i]) {

			mu[i] = -1;

			prime[++num] = i;

			f[i] = 1 + i;

			exmin[i] = 1;

		}

		for(int j = 1; j <= num; ++j) {

			int t = prime[j] * i; if (t > N) break;

			np[t] = 1;

			if (i % prime[j] == 0) {

				mu[t] = 0;

				f[t] = exmin[i] + prime[j] * f[i];

				exmin[t] = exmin[i];

				break;

			}

			mu[t] = -mu[i];

			f[t] = f[i] * (1 + prime[j]);

			exmin[t] = f[i];

		}

	}

}

int Qsum(int x) {

	int ret = 0;

	for(; x; x -= x & -x)

		ret += bit[x];

	return ret;

}

void add(int x, int s) {

	for(; x <= up; x += x & -x)

		bit[x] += s;

}

void update(int d, int s) {

	for(int i = d, j = 1; i <= up; i += d, ++j)

		add(i, s * mu[j]);

}

struct node1 {int n, m, a, id;} Q[N + 3];

struct node2 {int f, id;} F[N + 3];

bool cmp1(node1 X, node1 Y) {return X.a < Y.a;}

bool cmp2(node2 X, node2 Y) {return X.f < Y.f;}

int ans[N + 3];

int main() {

	shai();

	int T;

	read(T);

	for(int i = 1; i <= T; ++i) {

		read(Q[i].n); read(Q[i].m); read(Q[i].a);

		Q[i].id = i;

		if (Q[i].n > Q[i].m) swap(Q[i].n, Q[i].m);

		up = max(up, Q[i].m);

	}

	sort(Q + 1, Q + T + 1, cmp1);

	for(int i = 1; i <= up; ++i)

		F[i].f = f[i], F[i].id = i;

	sort(F + 1, F + up + 1, cmp2);

	int n, m, a, tmp = 1;

	for(int i = 1; i <= T; ++i) {

		n = Q[i].n; m = Q[i].m; a = Q[i].a;

		while (tmp <= up && F[tmp].f <= a)

			update(F[tmp].id, F[tmp].f), ++tmp;

		int ret = 0;

		for(int j = 1, la = 1; j <= n; j = la + 1) {

			la = min(n / (n / j), m / (m / j));

			ret += (Qsum(la) - Qsum(j - 1)) * (n / j) * (m / j);

		}

		ans[Q[i].id] = ret & ((1u << 31) - 1);

	}

	for(int i = 1; i <= T; ++i)

		printf("%d\n", ans[i]);

	return 0;

}