题目描述

Aki 定义一种“Aki-素数”：奇数 $x$ 同时满足：

1. $x$ 是质数；
2. $\frac{x+1}{2}$ 也是质数。

现在有 $Q$ 次查询。每次给出两个数 $l_i,r_i$，请输出区间内满足 $l_i\le x\le r_i$ 的 Aki-素数个数。

输入格式

第一行 $Q$；接着 $Q$ 行：$l_i\ r_i$

$1\le Q\le 10^5$，$1\le l_i\le r_i\le 10^5$。

输出格式

按题意输出结果。

1
3 7

2

Hint

样例解释： 满足条件的数是3和5。