A15365. LCM Sum (hard version)

We are sum for we are many

Some Number



This version of the problem differs from the previous one only in the constraint on $t$ . You can make hacks only if both versions of the problem are solved.

You are given two positive integers $l$ and $r$ .

Count the number of distinct triplets of integers $(i, j, k)$ such that $l \le i < j < k \le r$ and $\operatorname{lcm}(i,j,k) \ge i + j + k$ .

Here $\operatorname{lcm}(i, j, k)$ denotes the [least common multiple (LCM)](https://en.wikipedia.org/wiki/Least_common_multiple) of integers $i$ , $j$ , and $k$ .

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $\bf{1 \le t \le 10^5}$ ). Description of the test cases follows.

The only line for each test case contains two integers $l$ and $r$ ( $1 \le l \le r \le 2 \cdot 10^5$ , $l + 2 \le r$ ).

For each test case print one integer — the number of suitable triplets.

In the first test case, there are $3$ suitable triplets:

- $(1,2,3)$ ,
- $(1,3,4)$ ,
- $(2,3,4)$ .

In the second test case, there is $1$ suitable triplet:

- $(3,4,5)$ .