P3455 [POI 2007] ZAP-Queries

A cryptographer is trying to break a cipher called BSA. He found that while breaking a message, he also needs to answer the following question: Given $a,b,d$, count the number of pairs $(x,y)$ such that $1 \leq x \leq a$, $1 \leq y \leq b$, and $\gcd(x,y)=d$. Because there are so many problems to solve, he asks for your help.

The first line contains an integer $n$, the number of queries. Each of the next $n$ lines contains three integers $a,b,d$.

For each query, output a single integer representing the answer.

Constraints For all testdata, it is guaranteed that $1 \leq n \leq 5 \times 10^4$, $1 \leq d \leq a,b \leq 5 \times 10^4$. Translated by ChatGPT 5