505037 - 破解密码

【题目描述】破解密码(ZAP)

密码学家破解密码时发现,他还需要回答这样一种问题:给出a,b,d,求满足1≤x≤a,1≤y≤b,且gcd(x,y)=d的二元组(x,y)的数量。

输入

第一行一个整数n(1≤n≤5×10^4),代表要回答的问题个数。 接下来n行,每行三个整数a,b,d(1≤d≤a,b≤5×10^4)。

输出

对于每组询问,输出一个整数代表答案。

样例

输入

2
4 5 2
6 4 3

输出

3
2
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题