Counting Ordered Pairs with a Given GCD

Time limit2sMemory limit128 MB

Summary

Count ordered pairs (x, y) with x <= a, y <= b and gcd(x, y) = d for up to 50,000 queries.

Level: Medium6 of 10
Topics: Number theory, Math, Combinatorics
Solved: No attempts yet

Problem

Given three integers a, b, and d, count the number of ordered pairs of positive integers (x, y) that satisfy all of the following conditions:

1 <= x <= a
1 <= y <= b
gcd(x, y) = d

Input

Several queries are given in one input file. The first line contains the number of queries N. Each of the next N lines contains three integers a, b, and d describing one query.

Output

For each query, print its answer on its own line.

Constraints

1 <= N <= 50,000
1 <= a, b, d <= 50,000
d <= a
d <= b

Hint

For the first query in the visible test case, there are three ordered pairs: (2, 2), (2, 4), and (4, 2). For the second query, there are two ordered pairs: (3, 3) and (6, 3).

Examples1

Example 1
Input
```
2
4 5 2
6 4 3
```
Expected output
```
3
2
```