题目描述

满足“$N$ 和 $(N+1)÷2$ 都是素数”的奇数 $N$，称为2017 类似数。

现在给出 $Q$ 个查询。

对于第 $i$ 个查询（$1 \leq i \leq Q$），给出两个奇数 $l_i$ 和 $r_i$，请你求出满足 $l_i \leq x \leq r_i$ 且 $x$ 是2017 类似数的奇数 $x$ 的个数。

输入格式

输入以如下格式从标准输入读入：

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

输出格式

对于每个查询 $i$（$1 \leq i \leq Q$），输出一行，表示该查询的答案 $x$ 的个数。

输入输出样例 #1

输入 #1

1
3 7

输出 #1

2

输入输出样例 #2

输入 #2

4
13 13
7 11
7 11
2017 2017

输出 #2

1
0
0
1

输入输出样例 #3

输入 #3

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

输出 #3

4
4
1
1
1
2

说明/提示

限制条件

• $1 \leq Q \leq 10^5$
• $1 \leq l_i \leq r_i \leq 10^5$
• $l_i$、$r_i$ 均为奇数
• 所有输入均为整数

样例解释 1

• $3$ 和 $(3+1)÷2=2$ 都是素数，因此 $3$ 是2017 类似数。
• $5$ 和 $(5+1)÷2=3$ 都是素数，因此 $5$ 是2017 类似数。
• $7$ 是素数，但 $(7+1)÷2=4$ 不是素数，因此 $7$ 不是2017 类似数。 因此，查询 $1$ 的答案是 $2$。

样例解释 2

请注意，$2017$ 也是2017 类似数。