题目描述

我们称一个奇数$N$与2017相似，当且仅当$N$和$(N+1)/2$都是素数时。

给定$Q$个查询。

在第$i$个查询中，给定两个奇数$l_i$和$r_i$，找出与2017相似的奇数$x$的数量，满足$l_i \leq x \leq r_i$。

约束条件

• $1 \leq Q \leq 10^5$
• $1 \leq l_i \leq r_i \leq 10^5$
• $l_i$和$r_i$都是奇数。
• 所有输入值均为整数。

输入

从标准输入中以以下格式给出输入：

$Q$ $l_1$ $r_1$ $\vdots$ $l_Q$ $r_Q$

输出

打印$Q$行。第$i$行$(1 \leq i \leq Q)$应包含对第$i$个查询的响应。

示例输入1

1
3 7

示例输出1

2

• $3$与2017相似，因为$3$和$(3+1)/2=2$都是素数。
• $5$与2017相似，因为$5$和$(5+1)/2=3$都是素数。
• $7$不与2017相似，因为$(7+1)/2=4$不是素数，尽管$7$是素数。

因此，对于第一个查询的响应应为$2$。

示例输入2

4
13 13
7 11
7 11
2017 2017

示例输出2

1
0
0
1

注意，$2017$也与2017相似。

示例输入3

6
1 53
13 91
37 55
19 51
73 91
13 49

示例输出3

4
4
1
1
1
2