素数个数

问题描述

T次询问，每次询问：给定一个区间$【L，R】$，求该区间范围里素数的个数。

输入格式

第一行一个整数 $T$ ，表示 $T$ 次询问
下面 $T$ 行，每行两个数$l，r$，$（l\leq r)$表示一个区间。

输出格式

T个整数，表示[$l，r$]之间素数的个数。

输入样例1

2
2 10
10 20

输出样例1

4
4

数据范围

$2\leq T\leq 10^5,2\leq l,r\leq 10^8$