Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Odd Prime

By Zeronfinity · Limits 1s, 512 MB

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

InputOutput
3
1 10
11 31
2 2
3
5
0

Statistics

52% Solution Ratio

game_overEarliest, Jan '20

moshiur_cse15Fastest, 0.1s

InsideOutLightest, 524 kB

tahsin_protikShortest, 982B

Submit

 IIUCPC 2020 Selection Contest Jan '20 