题目描述

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

输入格式

第一行一个整数N（1<=N<=100000）； 接下来N行，每行两个整数A、B（1<=A<=B<=100000），用空格隔开，表示一个区间范围。

输出格式

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

样例输入

2
2 8
1 13

样例输出

4
6

样例解释

1. 第一个区间是2到8，该区间内的素数依次为2、3、5、7，共4个，因此输出4；
2. 第二个区间是1到13，该区间内的素数依次为2、3、5、7、11、13，共6个，因此输出6。