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.