## The Third Cellar

View as PDFAfter travelling through the secret passage, also know as the "Communists' Road", they entered the third cellar. This is rumoured to be the entrance to the Phantom's house on the lake. In the third cellar are a bunch of trompe-l'œil, used for the background scenes by the opera house (back then they only have paintings to make a 3D looking background). You find 6 trompe-l'œil on each side. Each one has one and only one decimal digit. The numbers on each side assembles to a 6 digit number. The Persian explains: the Phantom really likes primes. The two numbers here represents a left-closed, right-open bounded interval, and the number of primes in this interval determines how many stones you must drop into the hole beside a boulder. One stone will be dropped every second, and the boulder will only move out of the way after you stopped at the right number for a second. Otherwise, the boulder will roll over all of you. Since Christine's life is in more danger now, you get the same amount of time as before, 2 seconds, to solve this problem.

But really, the Phantom knows that you just wrote your program the easiest way possible, and doesn't scale up for the challenge. Poor you have to rewrite your program more efficiently.

#### Input Specification

The first line is the number , always smaller than 20, the number of test cases to follow. The next lines are two natural numbers, as written on the trompe-l'œil, which are guaranteed to be smaller than .

#### Output Specification

Output the number of stones they need to drop to move the boulder, while not killing themselves.

#### Sample Input

```
2
1 1000
1000 4000
```

#### Sample Output

```
168
382
```

## Comments

Last one's timing out.

Yes, it is. There are efficient algorithms to find all the primes from to that are much faster than just checking if each number is prime individually. One example is the Sieve of Eratosthenes.

bam