当前没有测试数据。

D - 2017-like Number

Score : $400$ points

Problem Statement

We say that a odd number $N$ is similar to 2017 when both $N$ and $(N+1)/2$ are prime.

You are given $Q$ queries.

In the $i$-th query, given two odd numbers $l_i$ and $r_i$, find the number of odd numbers $x$ similar to 2017 such that $l_i ≤ x ≤ r_i$.

Constraints

• $1≤Q≤10^5$
• $1≤l_i≤r_i≤10^5$
• $l_i$ and $r_i$ are odd.
• All input values are integers.

Input

Input is given from Standard Input in the following format:

$Q$

$l_1$ $r_1$

$:$

$l_Q$ $r_Q$

Output

Print $Q$ lines. The $i$-th line $(1≤i≤Q)$ should contain the response to the $i$-th query.

1
3 7

2

• $3$ is similar to 2017, since both $3$ and $(3+1)/2=2$ are prime.
• $5$ is similar to 2017, since both $5$ and $(5+1)/2=3$ are prime.
• $7$ is not similar to 2017, since $(7+1)/2=4$ is not prime, although $7$ is prime.

Thus, the response to the first query should be $2$.

4
13 13
7 11
7 11
2017 2017

1
0
0
1

Note that $2017$ is also similar to 2017.

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

4
4
1
1
1
2