LCM Sum (hard version)

题意翻译

给定正整数 $l,r$，求满足 $\operatorname{lcm}(i,j,k) \ge i+j+k$ 且 $l \le i < j < k \le r$ 的三元组$(i,j,k)$的数量。 输入包含 $T$ 组数据（$1 \le T \le 10^5$），对于每组数据，$1 ≤ l ≤ r ≤ 2\times 10^{5}$。

题目描述

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.

输入输出样例

输入样例 #1

5
1 4
3 5
8 86
68 86
6 86868

输出样例 #1

3
1
78975
969
109229059713337

说明

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

题目大意：
给定两个正整数 l 和 r，计算满足条件 lcm(i,j,k) ≥ i+j+k 且 l ≤ i < j < k ≤ r 的不同整数三元组 (i,j,k) 的数量。

输入输出数据格式：
输入包含 T 组数据（1 ≤ T ≤ 10^5），每组数据包含两个整数 l 和 r（1 ≤ l ≤ r ≤ 2×10^5，l + 2 ≤ r）。

输出对于每组数据，输出一个整数，表示满足条件的三元组的数量。

输入输出样例：
输入样例 #1：
5
1 4
3 5
8 86
68 86
6 86868

输出样例 #1：
3
1
78975
969
109229059713337题目大意： 给定两个正整数 l 和 r，计算满足条件 lcm(i,j,k) ≥ i+j+k 且 l ≤ i < j < k ≤ r 的不同整数三元组 (i,j,k) 的数量。 输入输出数据格式： 输入包含 T 组数据（1 ≤ T ≤ 10^5），每组数据包含两个整数 l 和 r（1 ≤ l ≤ r ≤ 2×10^5，l + 2 ≤ r）。 输出对于每组数据，输出一个整数，表示满足条件的三元组的数量。 输入输出样例： 输入样例 #1： 5 1 4 3 5 8 86 68 86 6 86868 输出样例 #1： 3 1 78975 969 109229059713337