思路

由于 $l$ 和 $r$ 的范围可以达到 $10^{18}$，暴力枚举所有三元组是不可行的。我们需要通过数学分析来简化问题。

1. 简化条件 根据条件 $l \leq a < b < c \leq r$，我们知道 $\max(a, b, c) = c$ 且 $\text{sum}(a, b, c) = a+b+c$。 因此，核心不等式条件可以改写为： $c < \text{lcm}(a, b, c) < a + b + c$

2. 分析 $\text{lcm}(a, b, c)$

题目内容

给定两个正整数 $l$ 和 $r$ ，请统计满足以下条件的三元组 $(a,b,c)$ 的个数：

• $l≤a＜b<c≤r$;

• $max(a, b, c)< lcm(a, b,c)< sum(a, b, c)$ .

【名词解释】

最大值：对于一组整数，它们的最大值记作 $max(·)$

最小公倍数：对于一组整数，能够被它们全部整除的最小正整数，记作 $lcm(·)$ 。

和：对于一组整数，它们的和，记作 $sum(·)$ 。

输入描述

第一行输入整数 $t(1 ≦t≦ 10^4)$ ，表示测试用例数;

接下来 $t$ 行，每行输入两个整数 $l$ 和 $r(1≦l≦r≦10^{18},r-l+1≧3)$ ，表示区间端点。

输出描述

对于每个测试用例，在一行输出一个整数，表示满足条件的三元组个数。

样例1

输入

3
1 10
3 5
1 10000

输出

1
0
2332

说明

在第一个测试用例中，符合条件的三元组有 $(3,4,6)$ ，其 $max(3,4,6)= 6,lcm(3,4.6)=12,sum(3,4,6)= 13$ ，满足条件;

在第二个测试用例中，没有符合条件的三元组。