[POI2007]ZAP-Queries

题目描述

密码学家正在尝试破解一种叫 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$。

输出格式


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

输入输出样例

输入样例 #1

2
4 5 2
6 4 3

输出样例 #1

3
2

说明

$1 \leq n \leq 5 \times 10^4$,$1 \leq d \leq a,b \leq 5 \times 10^4$