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>1p \gt 1 that has no positive integer divisors other than 11 and pp itself. Piyash read somewhere that all prime numbers except 22 are odd.

Unfortunately, for some reason he thought it means prime numbers can not have any odd digit in it. For example, even though 2323 is a prime number, he thought because 2323 is made of digits 22 and 33, 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, 3131 is an odd prime, but 2323 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 "xx yy" you have to tell how many odd primes exist within the range [x,y][x, y] inclusive.

Input

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

Next QQ lines each contain pair of integers xx and yy separated by space.

Constraints

1Q1041 \leq Q \leq 10^4

1xy1081 \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

Discussion

Statistics


52% Solution Ratio

game_overEarliest, Jan '20

moshiur_cse15Fastest, 0.1s

InsideOutLightest, 524 kB

tahsin_protikShortest, 982B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.