题目描述

桐桐想统计某个区间范围里的素数，例如，$A=2$，$B=10$，则 $A$ 和 $B$ 之间（包括 $A$、$B$）素数一共有 $4$ 个，分别为：$2, 3, 5, 7$。现在桐桐给出 $N$ 个区间范围，需要统计每个区间内的素数个数（包括区间端点）。

输入格式

第一行一个整数 $N$。
接下来 $N$ 行，每行两个整数 $A, B$，用空格隔开，表示一个区间范围。

输出格式

共 $N$ 行，每行一个整数，对应每个区间范围的素数个数。

样例

2
2 8
1 13

4
6

样例解释

• 第一个区间 $[2, 8]$ 内的素数有 $2, 3, 5, 7$，共 $4$ 个。
• 第二个区间 $[1, 13]$ 内的素数有 $2, 3, 5, 7, 11, 13$，共 $6$ 个。

数据范围

• $1 \le N \le 100000$
• $1 \le A \le B \le 100000$