题目描述

FGD 正在破解一段密码，他需要回答很多类似的问题：

对于给定的整数 $a,b$ 和 $d$，有多少正整数对$x,y$，满足$x\leq a,y\leq b$，并且 $\gcd (x,y)=d$。作为 FGD 的同学，FGD 希望得到你的帮助。

输入格式

本题有多组数据

第一行包含一个正整数，表示一共有 $T$ $(1\leq T \leq 5\times 10^4)$ 组询问。

接下来 $T$ 行，每行表示一个询问，每行三个正整数，分别为 $a,b,d$ $(1\leq d\leq a,b\leq 5\times 10^4)$。

输出格式

输出共 $T$ 行。第 $i$ 行表示对于第 $i$ 组询问，输出一个正整数，表示满足条件的整数对数。

2
4 5 2
6 4 3

3
2

样例解释

对于第一组询问，满足条件的整数对有 $(2,2),(2,4),(4,2)$；

对于第二组询问，满足条件的整数对有 $(6,3),(3,3)$。

数据规模与约定

$1\leq T,a,b,d \leq 5\times 10^4$ 且有 $d\leq a,b$

题目来源

[POI2007] Zap