Counting Coprime Pairs in Ranges

Given a number of queries. Each query consists of 5 integers: \(a, b, c, d, k\). For each query, count the number of pairs of integers \((x, y)\) such that:

• \(a \le x \le b\)
• \(c \le y \le d\)
• \(\gcd(x,y) = k\)

Recall that \(\gcd(x,y)\) is the greatest common divisor of \(x\) and \(y\). A useful observation is that if \(\gcd(x, y)=k\) then both \(x\) and \(y\) are divisible by \(k\). Let \(x=kx'\) and \(y=ky'\); then the condition becomes \(\gcd(x',y')=1\) with \(x'\) in \([\lceil a/k \rceil, \lfloor b/k \rfloor]\) and \(y'\) in \([\lceil c/k \rceil, \lfloor d/k \rceil]\).

The problem is then reduced to counting the number of coprime pairs \((x', y')\) in a given rectangle. This can be efficiently solved using the mobius function \(\mu(n)\) via the formula:

[ F(n, m)=\sum_{d=1}^{\min(n,m)} \mu(d)\left\lfloor \frac{n}{d} \right\rfloor \left\lfloor \frac{m}{d} \right\rfloor ]

Then, the answer for a query is computed by a standard inclusion‐exclusion technique: if \(L_1=\lceil a/k\rceil\), \(R_1=\lfloor b/k\rfloor\), \(L_2=\lceil c/k\rceil\) and \(R_2=\lfloor d/k\rfloor\), the number of coprime pairs in the ranges is

[ \text{answer} = F(R_1,R_2) - F(L_1-1,R_2) - F(R_1,L_2-1) + F(L_1-1,L_2-1). ]

If the adjusted ranges are invalid (i.e. if \(L_1>R_1\) or \(L_2>R_2\)), then the answer is 0.

inputFormat

The first line contains a single integer \(Q\) denoting the number of queries. Each of the following \(Q\) lines contains five space-separated integers \(a\), \(b\), \(c\), \(d\) and \(k\).

Note: It is guaranteed that all numbers are positive integers.

outputFormat

For each query, output a single integer on a new line representing the number of pairs \((x, y)\) satisfying the conditions.

sample

3
1 10 1 10 1
1 10 1 10 2
10 20 15 30 5

60
19
6