Prime number seems to be trending topic for programming contest. As such, Piyash, being an aspiring competitive programmer, started learning about theories and algorithms related to prime numbers. A prime number is a positive integer $p \gt 1$ that has no positive integer divisors other than $1$ and $p$ itself. Piyash read somewhere that all prime numbers except $2$ are odd.

Unfortunately, for some reason he thought it means prime numbers can not have any odd digit in it. For example, even though $23$ is a prime number, he thought because $23$ is made of digits $2$ and $3$, it can not be prime.

As we all know, this is not true at all. But for fun, let’s define an Odd Prime. An Odd Prime is a prime containing only odd digits. For example, $31$ is an odd prime, but $23$ is not.

Now, Piyash want to know how many such odd primes exist and asked for your help. You will be given a list of queries of the form "$x$$y$" you have to tell how many odd primes exist within the range $[x, y]$ inclusive.

Input

First line contains an integer representing the total number of queries $Q$.

Next $Q$ lines each contain pair of integers $x$ and $y$ separated by space.

Constraints

$1 \leq Q \leq 10^4$

$1 \leq x \leq y \leq 10^8$

Output

For each query print number of odd primes in that range.