4534. 破译密码
时间限制：1000 MS 内存限制：256 MB
题目描述
达达正在破解一段密码，他需要回答很多类似的问题： 对于给定的整数 a,b 和 d，有多少正整数对 x,y，满足 x≤a，y≤b，并且 gcd(x,y)=d。 作为达达的同学，达达希望得到你的帮助。 输入格式 第一行包含一个正整数 n，表示一共有 n 组询问。 接下来 n 行，每行表示一个询问，每行三个正整数，分别为 a,b,d。 输出格式 对于每组询问，输出一个正整数，表示满足条件的整数对数。 数据范围 1≤n≤50000,1≤d≤a,b≤50000 输入样例： ``` 2 4 5 2 6 4 3 ``` 输出样例： ``` 3 2 ``` 提示:gcd(x,y) 返回 x，y 的最大公约数。