问题描述

具体描述见教材p63：统计某个区间的素数,如A=2， B=10，则A和B之间（包括A，B)素数有一共有4个，分别是2，3，5，7。现在给出N个区间，问每个区间有多少个素数。

格式

输入

第1行一个整数$N (1 ≤ N ≤ 10^5)$。 后面有N行，每行两个整数$A，B (1 ≤ A ≤ B ≤ 10^6)$，用空格隔 开，表示一个区间范围。

输出

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

样例

2
2 8
1 13

4
6

限制

1s, 64MB.