有 $n$ 个询问，你需要统计 $L$ 到 $R$ 范围内，有多少个数是素数。

输入格式

第一行一个整数 $n$，表示询问个数。

接下来 $n$ 行，每行两个整数 $L$ 和 $R$。 

输出格式

对于每个询问，输出一个整数，表示这个区间素数的个数。

数据范围

对于 $50\%$ 的数据，满足 $1 \le L,R \le 5 \times 10^3，n \le 10^2$

对于 $70\%$ 的数据，满足 $1 \le L,R \le 5 \times 10^5，n \le 10^3$

对于 $100\%$ 的数据，满足 $1 \le L,R \le 5 \times 10^6，n \le 10^5$

样例输入

3
1 5
4 10
7 13

样例输出

3
2
3