← 返回题目列表

Codeforces · 2125/C

C. 数好数字

中文机器翻译题面 查看原题

素数是一个正整数,恰好有两个约数:$$$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$$$ 的好整数的数量。

示例

输入
复制

4
2 100
2 1000
13 37
2 1000000000000000000

输出
复制

21
227
7
228571428571428570