该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 9F. 莫比乌斯反演

时间限制：1000ms

空间限制：256MB

题目描述

为了打破“标题有什么算法这题就一定不用什么算法”的约定，这题真的是莫比乌斯反演。
密码学家正在尝试破解一种叫 BSA 的密码。
他发现，在破解一条消息的同时，他还需要回答这样一种问题：
给出 \(a,b,d\)，求满足 \(1 \leq x \leq a\)，\(1 \leq y \leq b\)，且 \(\gcd(x,y)=d\) 的二元组 \((x,y)\) 的数量。
因为要解决的问题实在太多了，他便过来寻求你的帮助。

输入格式

输入第一行一个整数 \(n\)，代表要回答的问题个数。
接下来 \(n\) 行，每行三个整数 \(a,b,d\)。

输出格式

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

样例输入

2
4 5 2
6 4 3

样例输出

3
2

数据范围及约定

对于全部的数据，保证 \(1 \leq n \leq 5 \times 10^4\)，\(1 \leq d \leq a,b \leq 5 \times 10^4\)。