After travelling through the secret passage, also known 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 assemble into a 6 digit number. The Persian explains: the Phantom really likes primes. The two numbers here represent 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, 1 second, 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

The time limit is now 1 second. Can the problem statement be changed to reflect that?

I am getting WA for all cases in test cases 1-8 and AC for test cases 9 and 10. Could anyone offer an explanation? For all cases I have computed otherwise its outputs the correct answer

I'm pretty sure your sieve is incorrect

This comment is hidden due to too much negative feedback. Click here to view it.

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