The Mirror

View as PDF

Submit solution

All submissions

Best submissions

Points: 5

Time limit: 1.0s

Memory limit: 64M

Author:

quantum

Problem type

Christine Daaé was kidnapped one night while singing on stage. Raoul, with the aid of the Persian, discovered that the Phantom was the kidnapper. The Persian believed that the easiest way to get to the Phantom's hiding place, which is on the lake under the Paris Opera House, in case you wonder, is from Christine's dressing room. On the corners of the mirror inside the dressing room were two numbers. The Persian recounted that the Phantom liked prime numbers, and the only way to open the secret passage behind the mirror is to knock on the mirror. The exact amount of times to knock is determined by the number of prime numbers between the two numbers shown, as a left-closed, right-open bounded interval. Since Christine's life is in danger, they expect you to solve it in one second, programmatically of course.

The Persian enlightens you on left-closed, right-open bounded intervals, because he fears that you will do it wrong and lose valuable time. An interval $[a, b)$ ~[a, b)~ is an interval from $a$ ~a~ to $b$ ~b~ including $a$ ~a~ but excluding $b$ ~b~, and is described as left-closed, right-open bounded interval.

But really, they just threatened to show the Phantom's fa^U

Input Specification

The first line is the number $N$ ~N~, such that $N \in \mathbb{N}, N \le 10$ ~N \in \mathbb{N}, N \le 10~, the number of test cases to follow. The next $N$ ~N~ lines are two numbers, as written on the mirror, which are guaranteed to be no more than 500.

Output Specification

Output the number of times they need to knock to open up the secret passage behind the mirror.

Sample Input

2
1 10
1 100

Sample Output

4
25

Explanation

There are 4 primes in $[1, 10)$ ~[1, 10)~: 2, 3, 5, 7.
There are 25 primes in $[1, 100)$ ~[1, 100)~: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Comments

38

jg119 commented on Nov. 19, 2015, 3:08 a.m.

Whats this joke? : "But really, they just threatened to show the Phantom's fa^U"

4

AlanCCCL2S18 commented on June 27, 2019, 1:02 a.m.

fa^U is probably "face". read the Wikipedia article about the phantom of the opera, I wont spoil it