素数是一个正整数,恰好有两个约数:$$$1$$$ 和它本身。前几个素数是 $$$2, 3, 5, 7, 11, \dots$$$。
正整数的质因数分解将其表示为质数的乘积。例如:
- $$$111$$$ 的质因数分解为 $$$3 \cdot 37$$$;
- $$$43$$$ 的质因数分解为 $$$43$$$;
- $$$12$$$ 的质因数分解为 $$$2 \cdot 2 \cdot 3$$$。
对于每个正整数,其素数分解都是唯一的(如果不考虑乘积中素数的顺序)。
我们称正整数 好 if 全部 质数分解至少由两位数字组成。例如:
- $$$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$$$ 的好整数的数量。
示例
输入复制
42 1002 100013 372 1000000000000000000
输出复制
21 227 7 228571428571428570