题目描述

翁老师认为如果一个正整数有且只有两个真因子，那么就可以叫做 真质数。

• $n$ 的真因子指的是小于 $n$ 的因子。例如 $6$ 的真因子有 $1,2,3$。

现在有 $T$ 组询问，每组询问希望你求一下 $l\sim r$ 有多少个数字是真质数。

输入格式

第一行输入一个正整数 $T$ 表示 $T$ 组询问。

接下来 $T$ 行，每行一个询问：$l,r$。

输出格式

输出一共输出 $T$ 行，每行一个整数代表答案。

3
1 100
333 500
100000 1000000

4
1
103

数据规模与约定

对于 $100\%$ 的数据：$1\leq T\leq 10^4$，$1\leq l\leq r\leq 10^9$。

• 子任务 1（30 分）：$T\leq 10$，$l\leq r\leq 2000$。
• 子任务 2（30 分）：$l\leq r\leq 10^5$。
• 子任务 3（40 分）：没有特殊限制