## 洛谷P3455 [POI2007][BZOJ1101]ZAP-Queries

### 题目

#### Description

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.
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\le a$ ， $y \le b$，并且 $gcd(x,y)=d$ 。作为FGD的同学，FGD希望得到你的帮助。

#### Input

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.

#### Output

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.

2
4 5 2
6 4 3

3
2