题目描述

33DAI 认为如果一个正整数有且只有两个真因子，那么就可以叫“真·质数”。

更具体的说，下面的 $f$ 函数可以返回一个 int 范围内的数是不是“真·质数”：

bool f(int x)
{
	int cnt = 0;
	for (int i = 1; i <= x - 1; i++)
		if (x % i == 0)
			cnt++;
	return cnt == 2;
}

33DAI 希望你帮他算算 $l\sim r$ 范围内有多少“真·质数”。

输入格式

第一行为一个正整数 $T$，表示 $T$ 组询问。

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

输出格式

输出 $T$ 行，第 $i$ 行为第 $i$ 个询问的答案。

3
1 100
333 500
100000 1000000

4
1
103

数据规模与约定

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

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