#include<iostream>
#include<cstring>
#include<vector>
#include<array>
using namespace std;
using LL = long long;

const int mod = 1e9 + 7;

void add(int &a, int b){
    a += b;
    if (a >= mod) a -= mod;
}

int mul(int a, int b){
    return 1LL * a * b % mod;
}

const int maxn = 1e5 + 5;
int mu[maxn];
vector<int> prime;
bool isPrime[maxn];

void init(){
    mu[1] = 1;
    for(int i = 2; i < maxn; i++){
        if (!isPrime[i]){
            prime.push_back(i);
            mu[i] = -1;
        }
        for(auto p : prime){
            if (i * p > maxn) break;
            isPrime[i * p] = true;
            if (p % i == 0) break;
            mu[i * p] = -mu[i];
        }
    }
}

int tr[maxn];

int lowbit(int x){
    return x & -x;
}

void modify(int x, int v){
    if (v < 0) v += mod;
    while(x < maxn){
        add(tr[x], v);
        x += lowbit(x);
    }
}

int sum(int x){
    int ans = 0;
    while(x){
        add(ans, tr[x]);
        x -= lowbit(x);
    }
    return ans;
}

int sum(int l, int r){
    return sum(r) - sum(l - 1);
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    init();
    const int N = 1e5;
    vector<vector<array<int, 3> > > query(N + 1);
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        int n, m, a;
        cin >> n >> m >> a;
        query[a].push_back({n, m, i});
    }

    auto f = [&](int x){
        return int(1LL * x * (x + 1) / 2 % mod);
    };

    vector<int> ans(q);
    for(int i = 1; i <= N; i++){
        for(int j = i; j <= N; j += i){
            int t = mu[j / i];
            if (t < 0) t += mod;
            t = mul(t, j);
            t = mul(t, j / i);
            modify(j, t);
        }
        for(auto [n, m, id] : query[i]){
            int t = min(n, m);
            int s = 0;
            for(int l = 1, r; l <= t; l = r + 1){
                r = min(n / (n / l), m / (m / l));
                add(s, mul(sum(l, r), mul(f(n / l), f(m / l))));
            }
            ans[id] = s;
        }
    }
    for(auto x : ans) cout << x << '\n';

}