问题描述

质数是正好有两个除数的正整数： $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