[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 \leq n \leq 50000$,$1 \leq d \leq a,b \leq 50000$

题目描述

Byteasar the Cryptographer works on breaking the code of BSA (Byteotian Security Agency). He has alreadyfound out that whilst deciphering a message he will have to answer multiple queries of the form"for givenintegers $a$, $b$ and $d$, find the number of integer pairs $(x,y)$ satisfying the following conditions: $1\le x\le a$,$1\le y\le b$,$gcd(x,y)=d$, where $gcd(x,y)$ is the greatest common divisor of $x$ and $y$". Byteasar would like to automate his work, so he has asked for your help. TaskWrite a programme which: reads from the standard input a list of queries, which the Byteasar has to give answer to, calculates answers to the queries, writes the outcome to the standard output. FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d。作为FGD的同学,FGD希望得到你的帮助。

输入输出格式

输入格式


The first line of the standard input contains one integer $n$ ($1\le n\le 50\ 000$),denoting the number of queries. The following $n$ lines contain three integers each: $a$, $b$ and $d$($1\le d\le a,b\le 50\ 000$), separated by single spaces. Each triplet denotes a single query.

输出格式


Your programme should write $n$ lines to the standard output. The $i$'th line should contain a single integer: theanswer to the $i$'th query from the standard input.

输入输出样例

输入样例 #1

2
4 5 2
6 4 3

输出样例 #1

3
2