Counting Ordered Pairs with a Given GCD

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. 1 <= x <= a
2. 1 <= y <= b
3. gcd(x, y) = d

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.

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

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

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).