题目描述

给定一个正整数 $m$ ，表示 $m$ 次查询，对于每个查询 $[l,$ $r]$，你需要找出该区间内的所有质数个数，并输出结果。

注意，这里的质数指的是大于等于 $2$ 的素数。

本题r范围由1e6变为2e6，请注意。

输入格式

一共 $m+1$ 行。

第一行包含一个正整数 $m$ ，表示查询次数。

下面 $m$ 行，每一行包含两个正整数 $l$ 和 $r$ ，表示查询区间 $[l$ , $r]$ 之间有多少个质数。

输出格式

一共 $m$ 行。

每行包含一个整数，表示当前查询区间内的质数数量。

样例

3
1 3
2 3
3 10

2
2
3

数据范围

$1<=m<=1e6$

$1<=l<=r<=2e6$