#include <cstdio>
#include <cassert>

#include <vector>
#include <algorithm>

using namespace std;

typedef long long int64;

const int MAX_VALUE = 50000;

vector<int> Primes, Mobius, Mertens;

vector< pair<int, int> > GetSegments(const int value) {
    vector<int> divisors, lesserDivisors, greaterDivisors;
    for (int d = 1; d * d <= value; ++d) {
        if (value % d == 0) {
            lesserDivisors.push_back(d);
            if (d < value / d)
                greaterDivisors.push_back(value / d);
        }
    }
    reverse(greaterDivisors.begin(), greaterDivisors.end());
    divisors = vector<int>(int(lesserDivisors.size()) + int(greaterDivisors.size()));
    merge(lesserDivisors.begin(), lesserDivisors.end(), greaterDivisors.begin(), greaterDivisors.end(), divisors.begin());
    vector< pair<int, int> > segments;
    segments.push_back(make_pair(value, 1));
    for (int i = 0; i + 1 < int(divisors.size()); ++i)
        segments.push_back(make_pair(value / (divisors[i] + 1), divisors[i + 1] - divisors[i]));
    return segments;
}

void Eratosthenes() {
    vector<bool> composite = vector<bool>(MAX_VALUE + 1, false);
    for (int i = 2; i <= MAX_VALUE; ++i) {
        if (composite[i])
            continue;
        Primes.push_back(i);
        if (1LL * i * i > MAX_VALUE)
            continue;
        for (int j = i * i; j <= MAX_VALUE; j += i)
            composite[j] = true;
    }
}

void BuildMobiusFunction() {
    vector<int> factorCount = vector<int>(MAX_VALUE + 1, 0);
    for (vector<int>::iterator p = Primes.begin(); p != Primes.end(); ++p)
        for (int value = *p; value <= MAX_VALUE; value += *p)
            ++factorCount[value];
    Mobius = vector<int>(MAX_VALUE + 1, 0);
    for (int i = 1; i <= MAX_VALUE; ++i) {
        if (factorCount[i] % 2 == 0)
            Mobius[i] = 1;
        else
            Mobius[i] = -1;
    }
    for (vector<int>::iterator p = Primes.begin(); p != Primes.end() && (*p) * (*p) <= MAX_VALUE; ++p)
        for (int value = (*p) * (*p); value <= MAX_VALUE; value += *p)
            Mobius[value] = 0;
}

void BuildMertensFunction() {
    Mertens = Mobius;
    for (int i = 1; i < int(Mertens.size()); ++i)
        Mertens[i] += Mertens[i - 1];
}

void Preprocess() {
    Eratosthenes();
    BuildMobiusFunction();
    BuildMertensFunction();
}

inline int Intersect(const pair<int, int> &x, const pair<int, int> &y) {
    if (x.first <= y.first)
        return max(0, x.second - y.first + 1);
    else
        return max(0, y.second - x.first + 1);
}

inline int64 CountPairs(int x, int y) {
    if (y < x)
        swap(x, y);
    int64 pairs = 0;
    vector< pair<int, int> > xSegments = GetSegments(x), ySegments = GetSegments(y);
    for (int i = 0, j = 0, dx = 0, dy = 0; i < int(xSegments.size()) && j < int(ySegments.size()); dx += xSegments[i++].second) {
        int length = Intersect(make_pair(dx + 1, dx + xSegments[i].second), make_pair(dy + 1, dy + ySegments[j].second));
        pairs += 1LL * length * xSegments[i].first * ySegments[j].first * (Mertens[dx + xSegments[i].second] - Mertens[dx]);
        if (dy + ySegments[j].second < dx + xSegments[i].second) {
            dy += ySegments[j++].second;
            length = Intersect(make_pair(dx + 1, dx + xSegments[i].second), make_pair(dy + 1, dy + ySegments[j].second));
            pairs += 1LL * length * xSegments[i].first * ySegments[j].first * (Mertens[dx + xSegments[i].second] - Mertens[dx]);
        }
    }
    /*for (int d = 1; d <= x; ++d)
        pairs += Mobius[d] * int64(x / d) * int64(y / d);*/
    return pairs;
}

int main() {
    assert(freopen("queries.in", "r", stdin));
    assert(freopen("queries.out", "w", stdout));
    Preprocess();
    int Q;
    assert(scanf("%d", &Q) == 1);
    for (; Q > 0; --Q) {
        int x, y, d;
        assert(scanf("%d %d %d", &x, &y, &d) == 3);
        printf("%lld\n", CountPairs(x / d, y / d));
    }
    return 0;
}