素数个数

题目描述

Orange在讲完数论后，给了你 $T$ 个询问，每次问你一个闭区间 $[l,r]$，你需要回答Orange区间内素数的个数。

输入格式

第一行为一个整数 $T(T \le 10^5)$。 之后的 $T$ 行，每行包含两个整数 $l,r(1\le l \le r \le 10^6)$，表示询问的区间。

输出格式

给出每个询问的答案，每个答案占一行。

样例 #1

样例输入 #1

4
2 3
1 10
11 12
14 15

样例输出 #1

2
4
1
0