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）。

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