Home

Contest: Task: Related: TaskC TaskE

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.

Sample Input 1

1
3 7

Sample Output 1

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$.

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that $2017$ is also similar to 2017.

Sample Input 3

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

Sample Output 3

4
4
1
1
1
2