# [POI2007]ZAP-Queries

## 题目描述

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``````