The Third Cellar

View as PDF
Submit solution
Points: 10
Time limit: 1.0s
Memory limit: 64M
Author:
quantum
Problem type

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 N, always smaller than 20, the number of test cases to follow. The next N lines are two natural numbers, as written on the trompe-l'œil, which are guaranteed to be smaller than 1\,000\,000.

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


  • 0
    omaewamoushindeiru  commented on Nov. 29, 2014, 12:55 a.m.

    Last one's timing out.


    • 6
      FatalEagle  commented on Nov. 29, 2014, 1:09 a.m. ← edited

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