Description
密码学家正在尝试破解一种叫 BSA 的密码。
他发现，在破解一条消息的同时，他还需要回答这样一种问题：
给出 a,b,d，求满足 1≤x≤a，1≤y≤b，且 gcd(x,y)=d 的二元组 (x,y) 的数量。
因为要解决的问题实在太多了，他便过来寻求你的帮助。
Input
输入第一行一个整数 n，代表要回答的问题个数。
接下来 n 行，每行三个整数 a,b,d。
Output
对于每组询问，输出一个整数代表答案。
HINT
对于全部的测试点，保证 1≤n≤5×104，1≤d≤a,b≤5×104。