CF1712E2 LCM Sum (hard version)

我们之和，因我们众多。 一些数字 本题与前一版本的区别仅在于 $ t $ 的约束条件。只有当两个版本的问题都被解决时，才能进行 hack。 给定两个正整数 $ l $ 和 $ r $。 请计算有多少个不同的整数三元组 $ (i, j, k) $ 满足 $ l \le i < j < k \le r $ 且 $ \operatorname{lcm}(i,j,k) \ge i + j + k $。 这里 $ \operatorname{lcm}(i, j, k) $ 表示整数 $ i $、$ j $、$ k $ 的最小公倍数。

每个测试点包含多组测试数据。第一行包含测试用例数 $ t $（$ 1 \le t \le 10^5 $）。接下来每组测试数据一行，包含两个整数 $ l $ 和 $ r $（$ 1 \le l \le r \le 2 \cdot 10^5 $，$ l + 2 \le r $）。

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

在第一个测试用例中，有 $ 3 $ 个满足条件的三元组： - $ (1,2,3) $， - $ (1,3,4) $， - $ (2,3,4) $。 在第二个测试用例中，有 $ 1 $ 个满足条件的三元组： - $ (3,4,5) $。 由 ChatGPT 4.1 翻译