题目描述

统计一个区间 $[A,B]$ 有多少素数。

输入格式

第一行一个整数 $n$，代表测试数据的组数（不超过 $10^5$）。 接下来每行 $2$ 个正整数 $1 \leq A \leq B \leq 10^7$。

输出格式

对每组输入，输出素数的个数。

3
1 100
1 10000
1 10000000

25
1229
664579