import sys
# 计算1-N中所有数的莫比乌斯函数，返回莫比乌斯函数的数组，下标从0开始
def get_mobius(N):
    prime_vals = []
    flag = [True] * (N+1)
    mobius = [0] * (N+1)        # 1的mobius函数没意义，默认为0

    for val in range(2, N+1):
        if flag[val]:
            prime_vals.append(val)
            mobius[val] = -1        # 质数的mobius函数肯定是-1, 因为只有自己本身这一个质因子

        # 从小到大枚举已经找出来的质数，直到找到val的最小质因子为止
        # 对于枚举到的每一个质数P，如果这个质数不是val的最小质因子
        # 那必然是val * P 这个数值的最小质因子，因为P比val的最小
        # 质因子小，同时P肯定是自己的最小质因子，所以P必然是val*P的
        # 最小质因子，同理，当P是val最小质因子时候，P同时是P和val
        # 的最小质因子，肯定也是P*val的最小质因子，就可以把P*val从
        # 质数里面筛掉，此算法可以保证每一个合数都是被其最小质因数
        # 筛掉的
        for p_val in prime_vals:
            if val * p_val > N:
                break

            flag[val * p_val] = False

            if val % p_val == 0:
                # val最小质因子是p_val, p_val自身也有一个质因子p_val, 所以在val * p_val 中p_val这个质因子至少出现了2次，因此莫比乌斯函数是0
                mobius[val * p_val] = 0
                break
            else:
                # p_val 比val 最小的质因子还小，说明p_val肯定在p_val*val质因数分解中刚刚第一次出现且次数为1，根据莫比乌斯函数的定义
                # val * p_val 相对起val而言，就刚好多了一个新的质因子p_val, 所以mobius[val * p_val]就是 mobius[val] 相反数
                mobius[val * p_val] = 0 - mobius[val]

    return mobius


mobius = get_mobius(50000)
S = [0] * (50000+1) # (bb//i) * mobius(i)序列的前缀和
for i in range(1, 50001):
    S[i] = S[i-1] + mobius[i]

n = int(input())
for _ in range(n):
    s = sys.stdin.readline().strip()
    a, b, d = map(int, s.split())

    '''
    等价于求[1,a//d]区间中取一个数，[1, b//d]区间中取一个数，有多少个数对是互质的
    设aa = a // d, bb = b // d
    根据容斥原理，答案应该是
    aa * bb
    - (aa//2) * (bb//2) - (aa//3) * (bb//3) .....       # 有1个公共质因子的数对
    + (aa//(2*3)) * (bb//(2*3)) + ......                # 有2个公共质因子的数对
    - (aa//(2*3*5)) * (bb//(2*3*5)) - .....             # 有3个公共质因子的数对
    .....

    变形后应该是
    aa * bb + sum{mobius(i) * (aa//i) * (bb//i)} 其中i是1, 2, 3, 4, ....... min(aa, bb)
    (aa//i)*(bb//i) 是一个分段函数，可以一段一段处理，每一段的数值乘以 mobius这个序列的某一区段的和，可以压缩
    时间复杂度
    '''
    aa, bb = a//d, b//d

    m = min(aa, bb)

    # 分段累加
    ans = aa * bb
    i = 1
    while i <= m:
        val1 = aa // i
        val2 = bb // i
        val = val1 * val2
        right_bound = min(aa // val1, bb // val2, m)
        ans += val * (S[right_bound] - S[i-1])
        i = right_bound + 1

    sys.stdout.write(str(ans)+'\n')