题目描述

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

对于给定的整数 $a,b$ 和 $d$，有多少正整数对 $x,y$，满足 $x \le a$，$y \le b$，并且 $\gcd(x,y)=d$。

作为达达的同学，达达希望得到你的帮助。

输入格式

第一行包含一个正整数 $n$，表示一共有 $n$ 组询问。

接下来 $n$ 行，每行表示一个询问，每行三个正整数，分别为 $a,b,d$。

输出格式

对于每组询问，输出一个正整数，表示满足条件的整数对数。

样例

输入样例：

2
4 5 2
6 4 3

输出样例：

3
2

样例解释

第一组询问：$a=4, b=5, d=2$

满足 $x \le 4, y \le 5$ 且 $\gcd(x,y)=2$ 的数对：

• $(2,2)$：$\gcd(2,2)=2$
• $(2,4)$：$\gcd(2,4)=2$
• $(4,2)$：$\gcd(4,2)=2$

共 $3$ 对。

第二组询问：$a=6, b=4, d=3$

满足 $x \le 6, y \le 4$ 且 $\gcd(x,y)=3$ 的数对：

• $(3,3)$：$\gcd(3,3)=3$
• $(6,3)$：$\gcd(6,3)=3$（注意 $y=3 \le 4$ 成立）

共 $2$ 对。

数据范围

• $1 \le n \le 50000$
• $1 \le d \le a,b \le 50000$

提示

$\gcd(x,y)$ 返回 $x，y$ 的最大公约数。

时空限制

• 时间限制：1 秒
• 空间限制：64 MB