问题描述

我们称一个奇数$N$为起遇质数，当且仅当$N$和$(N+1)/2$都是质数。 给定$Q$个查询，在第$i$个查询中，给定两个奇数$l_i$和$r_i$，找出满足$l_i \leq x \leq r_i$的起遇质数$x$的个数。

约束条件

• $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
:
l_Q r_Q

输出

输出$Q$行。第$i$行（$1 \leq i \leq Q$）应包含对第$i$个查询的响应。

样例输入1

1
3 7

样例输出1

2

• 3是起遇质数，因为3和$(3+1)/2=2$都是质数。
• 5是起遇质数，因为5和$(5+1)/2=3$都是质数。
• 7不是起遇质数，因为虽然7是质数，但$(7+1)/2=4$不是质数。 因此，第一个查询的响应应为2。

样例输入2

4
13 13
7 11
7 11
2017 2017

样例输出2

1
0
0
1

样例输入3

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

样例输出3

4
4
1
1
1
2