TLE + WA

t = int(input())
arr = [0] * 50010
zhi = [0] * 50010
bl = [0] * 50010
tot = 0
mu = [0] * 50010
mu[1] = 1
for i in range(2, 50001):
    if(not bl[i]):
        tot+=1;
        zhi[tot] = i
        mu[i] = -1
    for j in range(1, tot+1):
        if(zhi[j] * i > tot): break;
        bl[zhi[j] * i] = 1
        if(i % zhi[j] == 0) :
            mu[i*zhi[j]] = 0
            break
        mu[i*zhi[j]] = -mu[i]
for i in range(1, 50001):
    mu[i] += mu[i-1]
for i in range(t):
    a, b, c = map(int, input().split())
    l = 1
    x = a//c
    y = b//c
    ans = 0
    while(l <= min(x, y)):
        r = min(x//(x//l), y//(y//l))
        #print(r)
        ans += (mu[r] - mu[l-1]) * (x//r) * (y//r)
        l = r+1
    print(ans)