← 返回题目列表

Codeforces · 1712/E1

E1. LCM Sum(简易版)

中文机器翻译题面 查看原题

这个版本的问题与下一版本的不同之处仅在于对 $$$t$$$ 的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

给你两个正整数 $$$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$$$ 的最小公倍数 (LCM)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$\bf{1 \le t \le 5}$$$)。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le 2 \cdot 10^5$$$, $$$l + 2 \le r$$$)。

输出

对于每个测试用例,打印一个整数——合适的三元组的数量。

示例

输入 #1

5
1 4
3 5
8 86
68 86
6 86868

输出 #1

3
1
78975
969
109229059713337

注意

在第一个测试用例中,有 $$$3$$$ 合适的三元组:

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

在第二个测试用例中,有 $$$1$$$ 合适的三元组:

- $$$(3,4,5)$$$.