题目描述

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

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

输入格式

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

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

输出格式

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

样例

2
2 8
1 13

4
6

提示

1 很特殊，既不是素数，也不是合数。