题目描述

一个质数是一个只有两个因数：$1$ 和它自身的正整数。开头几个质数是 $2,3,5,7,11\cdots$。

一个正整数的质因数分解是把它表示为若干质数的积。例如：

• $111$ 的质因数分解是 $3\times 37$；
• $43$ 的质因数分解是 $43$；
• $12$ 的质因数分解是 $2\times 2\times 3$。

对于每个正整数，其质因数分解是唯一的（不考虑乘法中质数的顺序）。

当一个正整数的质因数分解中所有质因数都有至少两位，我们称它是好的。例如：

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

你需要计算 $l$ 和 $r$ 之间好的整数的数量（包括 $l$ 和 $r$）。

输入格式

多组数据。第一行一个整数 $t(1\le t\le 1000)$，表示数据组数。

对于每组数据，一行两个整数 $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