密码破译员 Byteasar 正在致力于破解 BSA（Byteotian Security Agency，字节国安全局）的密码。他已经发现，在破译信息时，他需要回答多个形如“对于给定的整数 $a$、$b$ 和 $d$，求满足以下条件的整数对 $(x, y)$ 的数量”的查询：

• $1 \le x \le a$
• $1 \le y \le b$
• $\gcd(x, y) = d$，其中 $\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数。

Byteasar 希望能自动化他的工作，因此他请求你的帮助。

任务

编写一个程序，完成以下工作：

• 从标准输入读取 Byteasar 需要回答的查询列表；
• 计算每个查询的答案；
• 将结果写入标准输出。

输入格式

标准输入的第一行包含一个整数 $n$ ($1 \le n \le 50\,000$)，表示查询的数量。接下来的 $n$ 行，每行包含三个整数 $a$、$b$ 和 $d$ ($1 \le d \le a, b \le 50\,000$)，以空格分隔。每个三元组代表一个查询。

输出格式

你的程序应向标准输出写入 $n$ 行。第 $i$ 行应包含一个整数，即第 $i$ 个查询的答案。

样例

输入 1

2
4 5 2
6 4 3

输出 1

3
2

说明 1

满足第一个查询的数对有：(2,2), (2,4) 和 (4,2)。满足第二个查询的数对有：(6,3) 和 (3,3)。