Description

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.

Input Format

The first line contains an integer $n$, the number of queries.

Each of the next $n$ lines contains three integers $a,b,d$.

Output Format

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

2
4 5 2
6 4 3

3
2

Hint

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