C. 统计好数
时间限制：2 秒
内存限制：512 兆字节

一个素数是恰好有两个因数的正整数：$1$ 和它本身。前几个素数为 $2,3,5,7,11,\dots$。

一个正整数的素因数分解是将其表示为素数乘积的形式。例如：

• $111 = 3 \cdot 37$；
• $43 = 43$；
• $12 = 2 \cdot 2 \cdot 3$。

每个正整数的素因数分解是唯一的（不考虑素数的顺序）。

如果一个正整数的素因数分解中所有素数至少包含两位数字，则称其为好数。例如：

• $343 = 7 \cdot 7 \cdot 7$ 不是好数；
• $111 = 3 \cdot 37$ 不是好数；
• $1111 = 11 \cdot 101$ 是好数；
• $43 = 43$ 是好数。

请计算区间 $[l, r]$（包含端点）中好数的个数。

输入
第一行包含一个整数 $t$（$1 \le t \le 10^3$）—— 测试用例数。

每个测试用例一行包含两个整数 $l$ 和 $r$（$2 \le l \le r \le 10^{18}$）。

输出
对于每个测试用例，输出一个整数 —— 区间 $[l, r]$ 中好数的个数。

样例
输入

4
2 100
2 1000
13 37
2 1000000000000000000

输出

21
227
7
228571428571428570