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.
Sample
| Input | Output |
|---|---|
3 1 10 11 31 2 2 | 3 5 0 |
