### 问题描述

假设一个三角形三条边为 $a$、$b$、$c$，定义该三角形的值 $v = a \times b \times c$。

现在有 $t$ 个询问，每个询问给定一个区间 $[l,r]$，问有多少个三条边都不相等的三角形的值 $v$ 在该区间范围内。

输入格式

第一行包含一个正整数 $t$，表示有 $t$ 个询问。

接下来 $t$ 行，每行有两个空格隔开的正整数 $l$、$r$，表示询问区间 $[l,r]$。

输出格式

输出共 $t$ 行，第 $i$ 行对应第 $i$ 个查询的三角形个数。

样例输入

4
1 10
30 50
60 200
200 400

样例输出

0
1
18
32

说明

在样例中，第二个区间 $[30,50]$ 的合法三角形的边长为 $2$、$4$、$5$。

评测数据规模

对于所有评测数据，$1\leq t \leq 10^5$，$1\leq l \leq r \leq 10^6$。