Description:


FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d。作为FGD的同学,FGD希望得到你的帮助。

Input:


第一行包含一个正整数n,表示一共有n组询问。(1<=n<= 50000)接下来n行,每行表示一个询问,每行三个正整数,分别为a,b,d。(1<=d<=a,b<=50000)

Output:


对于每组询问,输出到输出文件zap.out一个正整数,表示满足条件的整数对数。

Sample Input:


Sample Output:


题解:


这是一道十分经典的题,当我翻出来再做的时候就不会做了╮(╯▽╰)╭

首先该题是求 \(\sum_{i=1}^a \sum_{j=1}^b[gcd(i, j)=d]\)
不妨设 \(a \le b\)
\(\begin{align}\sum_{i=1}^a \sum_{j=1}^b[gcd(i, j)=d] &= \sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}[gcd(i, j)=1] \\ &= \sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}\sum_{g|gcd(i, j)}\mu (g) \\ &= \sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}\sum_{g|i\ and\ g|j}\mu (g) \\ &= \sum_{g=1}^{\lfloor \frac{a}{d} \rfloor} \lfloor \frac{\lfloor \frac{a}{d} \rfloor}{g} \rfloor \lfloor \frac{\lfloor \frac{b}{d} \rfloor}{g} \rfloor \mu (g) \end{align}\)

但这样还是 \(O(a)\) 的…… 我们发现 \(\lfloor \frac{\lfloor \frac{a}{d} \rfloor}{g} \rfloor\) 的取值种数很少,我们可以对于每一种取值分别算答案,因为同一种取值是连续的g,所以我们可以对 \(\mu\) 前缀和一下,然后就可以了。