题目描述

桐桐想统计某个区间范围里的素数，例如，A=2，B=10，则 A 和 B 之间（包括 A、B ）素数一共有4个，分别为：2，3，5，7。

现在桐桐给出 N 个区间范围，问每个区间有多少个素数。请你帮助她统计一下。

输入格式

第一行一个整数 N (1 <= N <= ${10}^5$ )；

后有 N 行，每行两个整数 A 和 B ( 1 <= A <= B <= ${10}^6$ )，用空格隔开，表示一个区间范围。

输出格式

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

样例

2
2 8
1 13

4
6