#include <iostream>

using namespace std;

typedef long long LL;

const int N = 50010;

int primes[N] , cnt;
bool st[N];
int mobius[N] , sum[N];

void init(int n)
{
    mobius[1] = 1;
    for(int i = 2 ; i <= n ; i++)
    {
        if(!st[i]) 
        {
            primes[cnt++] = i;
            mobius[i] = -1;
        }

        for(int j = 0 ; primes[j] <= n / i ; j++)
        {
            int t = primes[j] * i;
            st[t] = true;
            if(i % primes[j] == 0)
            {
                mobius[t] = 0;//t中至少包含2个primes[j]
                break;
            }
            mobius[t] = mobius[i] * -1;//primes[j]只出现一次，所以t的mobius值取决于i
        }
    }

    for(int i = 1 ; i <= n ; i++) sum[i] = sum[i - 1] + mobius[i];
}

int main()
{
    init(N - 1);

    int T;
    cin >> T;
    while(T--)
    {
        int a , b , d;
        cin >> a >> b >> d;
        a /= d , b /= d;
        int n = min(a , b);
        LL res = 0;
        for(int l = 1 , r ; l <= n ; l = r + 1)
        {
            r = min(n , min(a / (a / l) , b / (b / l)));
            //x最远跳到的位置g(x) = t / (t / x)，因为要使a/l和b/l的值都不变，所以要取跳的位置的min
            res += (sum[r] - sum[l - 1]) * (LL)(a / l) * (b / l);
            //在x∈[l,r]上，a/x和b/x的值是不变的，所以只要求出l~r上mobius的和*分式的值即可
        }
        cout << res << endl;
    }
    return 0;
}