To solve the subtask, loop over all pairs of candidate integers and check if they are relatively prime. To check if two integers ~x~ and ~y~ are relatively prime, it suffices to see if there is any number between ~2~ and ~\min(x, y)~ which divides both of them.

To solve the problem fully, we'll assume that ~A = C = 1~. If we can solve this problem then we can use inclusion-exclusion to compute the answer for arbitrary values of ~A~ and ~C~. If the number of pairs of relatively prime integers ~(x, y)~ where ~1 \le x \le B~ and ~1 \le y \le D~ is ~f(x, y)~, the answer would then be ~f(B, D) - f(A-1, D) - f(B, C-1) + f(A-1, C-1)~.

We now need to compute the number of pairs of coprime integers ~(x, y)~ such that ~1 \le x \le B~ and ~1 \le y \le D~.

For those familiar with Möbius inversion, it can be shown that the desired answer is equal to

$$\displaystyle \sum_{i=1}^{\min(B, D)} \mu(i) \left\lfloor \frac B i \right\rfloor \left\lfloor \frac D i \right\rfloor$$

With a sieve, one can precompute ~\mu(i)~ up to ~10^7~ in ~\mathcal O(10^7 \log \log 10^7)~.

For those unfamiliar with Möbius inversion, here is a non-rigorous way to approach the problem. One can start by trying to count all pairs of integers which are not relatively prime. One way to get started is by counting how many pairs of integers have 2 as a common factor, then 3, then 5, and enumerating all the primes up to ~\min(B, D)~. This produces an overestimate for the number of pairs of integers which are not relatively prime - for example, pairs of integers which have 6 as a common factor have been counted twice in this approach. We can try to compensate for the overcounting by then subtracting away the same count where pairs of integers have ~pq~ as a common factor, for distinct primes ~p~ and ~q~. This, also, is overcounting. Pairs of integers which have 30 as a common factor were included 3 times for 2, 3, and 5, and removed 3 times for 6, 10, and 15. We would therefore need to add these in again.

In effect, we need to enumerate over all integers ~n~ and count the number of primes that divide them. If ~n~ is square-free - that is, it is not divisible by ~k^2~ for some ~k > 1~, then we either add to the count if there are an odd number of prime divisors. Otherwise, the count is even and we subtract.