The Third Cellar

View as PDF

Submit solution


Points:10
Time limit:2.0s
Memory limit:32M
Author:

Problem type

After 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 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


  • -3
    u_yousafzai54
     commented on April 19, 2017

    All of my test cases work except for 4. Why?


  • 1
    BMP
     commented on Nov. 28, 2014
    Suggestions?

    Last one's timing out.


    • 2
      FatalEagle
       commented on Nov. 28, 2014

      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.


      • 1
        BMP
         commented on Dec. 1, 2014

        bam