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

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int mod = 1e9 + 7;

int mult(int a, int b)
{
	return (LL) a * b % mod;
}
int add(int a, int b)
{
	return a + b < mod ? a + b : a + b - mod;
}
int sub(int a, int b)
{
	return a - b >= 0 ? a - b : a - b + mod;
}



const int N = 1 << 17;
int pr[N];

int mu[N];
int inv[N];
int g[N];


int f2(int n)
{
	return mult(mult(n, n + 1), inv[2]);
}

struct Fenwick
{
	int n;
	vector<int> v;
	
	void init(int _n)
	{
		n = _n;
		v.assign(n, 0);
	}
	
	void upd(int i, int x)
	{
		for (; i < n; i |= (i + 1))
			v[i] = add(v[i], x);
	}
	
	int query(int i)
	{
		LL ans = 0;
		for (; i >= 0; i = (i & (i + 1)) - 1)
			ans = add(ans, v[i]);
		return ans;
	}
}F;


VI idxQ[N];
int nQ[N], mQ[N], maxA[N];

int ans[N];
void solve(int i)
{
	
	int n = nQ[i];
	int m = mQ[i];
	
	int a = 1;
	while(a <= n && a <= m)
	{
		int rA = min(n / (n / a), m / (m / a));
		
		int cur = mult(f2(n / a), f2(m / a));
		cur = mult(cur, sub(F.query(rA), F.query(a - 1)));
		ans[i] = add(ans[i], cur);
		
		a = rA + 1;
	}
}


void init()
{
	inv[1] = 1;
	FOR(i, 2, N)
		inv[i] = mult(mod - mod / i,  inv[mod % i]);		
	
	mu[1] = 1;
	FOR(p, 2, N)
	{
		if(pr[p] != 0)
		{
			if((p / pr[p]) % pr[p] == 0)
				mu[p] = 0;
			else
				mu[p] = sub(0, mu[p / pr[p]]);
			continue;
		}
			
		mu[p] = mod - 1;
		for(int j = 2 * p; j < N; j += p)
			pr[j] = p;
	}
	F.init(N);
	FOR(d, 1, N)
	{
		for(int a = d; a < N; a += d)
		{
			int coef = mult(mu[a / d], inv[d]);
			coef = mult(coef, mult(a, a));
			F.upd(a, coef);
		}
		
		for(int i : idxQ[d])
			solve(i);
	}
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int q;
	cin >> q;
	FOR(i, 0, q)
	{
		cin >> nQ[i] >> mQ[i] >> maxA[i];
		
		idxQ[maxA[i]].PB(i);
	}

	
	init();
	
		
	FOR(i, 0, q)
		cout << ans[i] << "\n";

	return 0;
}