题目描述

密码学家正在尝试破解一种叫 BSA 的密码。他发现，在破解一条消息的同时，他还需要回答这样一种问题：给出 a,b,d，求满足 1≤x≤a，1≤y≤b，且gcd(x,y)=d 的二元组 (x,y)(x,y) 的数量。
因为要解决的问题实在太多了，他便过来寻求你的帮助。

输入格式：

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

输出格式：

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

输入样例#1：

2
4 5 2
6 4 3

输出样例#1：

3
2