P3956Zap | ||
|
问题描述
FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d。作为FGD的同学,FGD希望得到你的帮助。
输入格式
第一行包含一个正整数n,表示一共有n组询问。(1<=n<= 50000)
接下来n行,每行表示一个询问,每行三个正整数,分别为a,b,d。(1<=d<=a,b<=50000)
输出格式
对于每组询问,输出到输出一个正整数,表示满足条件的整数对数。
样例输入 1
2
4 5 2
6 4 3
样例输出 1
3
2
样例输入 2
3
2 3 1
8 7 3
15 15 15
样例输出 2
5
3
1
样例输入 3
5
1 1 1
4 2 2
9 3 3
16 4 4
25 5 5
样例输出 3
1
2
3
4
5
提示
样例1说明:
对于第一组询问,满足条件的整数对有(2,2),(2,4),(4,2)。对于第二组询问,满足条件的整数对有(6,3),(3,3)。
来源 poi2007