#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
#define meow(cat...) fprintf(stderr, cat)

const ll MaxN = 1e5 + 10;

struct query
{
    ll n, m, a, id;
} Q[MaxN];

std::pair<ll, ll> p[MaxN];
ll q, cnt, pr[MaxN], vis[MaxN];
ll c[MaxN], g[MaxN], mu[MaxN], ans[MaxN];

ll lowbit(ll x) { return x & (-x); }
ll cmp(query a, query b) { return a.a < b.a; }

void add(ll x, ll v)
{
    while(x < MaxN)
        c[x] += v, x += lowbit(x);\
}

ll qry(ll x)
{
    ll res = 0;
    while(x)
        res += c[x], x -= lowbit(x);
    return res;
}

ll qry(ll l, ll r) { return qry(r) - qry(l - 1); }

inline ll read()
{
    ll x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0')
        ch = getchar();
    while (ch <= '9' && ch >= '0')
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}

ll solve(ll n, ll m)
{
    ll res = 0;
    for(ll l = 1, r; l <= std::min(n, m); l = r + 1)
    {
        r = std::min(n / (n / l), m / (m / l));
        res += qry(l, r) * (n / l) * (m / l);
    }
    return res;
}

void init()
{
    mu[1] = 1;
    for(ll i = 2; i < MaxN; i++)
    {
        if(!vis[i]) pr[++cnt] = i, mu[i] = -1;
        for(ll j = 1; j <= cnt && i * pr[j] < MaxN; j++)
        {
            vis[i * pr[j]] = 1;
            if(i % pr[j] == 0) break;
            mu[i * pr[j]] = -mu[i];
        }
    }
    for(ll i = 1; i < MaxN; i++)
    {
        for(ll j = 1; j * j <= i; j++)
            if(i % j == 0) 
            {
                p[i].first += j;
                if(j * j != i)
                    p[i].first += i / j;
            }
        p[i].second = i;
    }
    std::sort(p + 1, p + MaxN);
}

signed main()
{   
    q = read(), init();
    for(ll i = 1; i <= q; i++)
        Q[i].n = read(), Q[i].m = read(), Q[i].a = read(), Q[i].id = i;
    std::sort(Q + 1, Q + q + 1, cmp);
    for(ll i = 1, now = 1; i <= q; i++)
    {
        while(p[now].first <= Q[i].a && now < MaxN)
        {
            for(ll k = p[now].second; k < MaxN; k += p[now].second)
                add(k, p[now].first * mu[k / p[now].second]);
            now = now + 1;
        }
        ans[Q[i].id] = solve(Q[i].n, Q[i].m);
    }
    for(ll i = 1; i <= q; i++)
        printf("%lld\n", ans[i] % (1ll << 31));
    return 0;
}