AT_abc084_d.[ABC084D] 2017-like Number

满足“$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 \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 类似数。

由 ChatGPT 4.1 翻译