HS12PRIM - Classification from Erdős and Selfridge

Erdős Pál and John Selfridge classified prime numbers in this way: for a prime p, if the largest prime factor of p-1 is 2 or 3, then p is in class one. Otherwise, p is in class c+1 where c is the largest of the classes of the prime factors of p-1. We put p=2 in class one. For example, p=89 is in class three, because p-1=2^3*11 and here 2 is in class one, but 11 is in class two (because 11-1=2*5 and here 2 and 5 are in class one). Your task is to count the number of primes in each class up to class thirteen for a given (closed) interval.

Input

The first line contains the number of test cases T, where T≤1000. Each of the following T lines contains two integers a,b where 0≤a≤b≤50000000. There are 4 input sets for 10 points.

Output

Output the case number, followed by the distribution of the primes in each class up to class 13 in the (closed) interval [a,b]. See the sample input/output for the correct format!

Example

Input:
3
2 100
23 23
0 50000000

Output:
Case 1:
There are 10 primes in class 1.
There are 9 primes in class 2.
There are 5 primes in class 3.
There are 1 primes in class 4.
There are 0 primes in class 5.
There are 0 primes in class 6.
There are 0 primes in class 7.
There are 0 primes in class 8.
There are 0 primes in class 9.
There are 0 primes in class 10.
There are 0 primes in class 11.
There are 0 primes in class 12.
There are 0 primes in class 13.

Case 2:
There are 0 primes in class 1.
There are 0 primes in class 2.
There are 1 primes in class 3.
There are 0 primes in class 4.
There are 0 primes in class 5.
There are 0 primes in class 6.
There are 0 primes in class 7.
There are 0 primes in class 8.
There are 0 primes in class 9.
There are 0 primes in class 10.
There are 0 primes in class 11.
There are 0 primes in class 12.
There are 0 primes in class 13.

Case 3:
There are 54 primes in class 1.
There are 14196 primes in class 2.
There are 364182 primes in class 3.
There are 1029984 primes in class 4.
There are 939493 primes in class 5.
There are 458831 primes in class 6.
There are 150902 primes in class 7.
There are 34878 primes in class 8.
There are 7085 primes in class 9.
There are 1310 primes in class 10.
There are 203 primes in class 11.
There are 15 primes in class 12.
There are 1 primes in class 13.

Warning: A naive algorithm will probably solve only the first input set.


Added by:Robert Gerbicz
Date:2012-09-18
Time limit:1s-26.83s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:High School Programming League 2012/13

hide comments
2016-06-30 11:04:02 Bhuvnesh Jain
@Robert, could you please tell why I am getting TLE? Is my algorithm of pre-computation slow or more optimisations are required? The complexity for pre-computation is O(n + plogp), where n = 50000000 and p = number of primes below 50000000.

Last edit: 2016-06-30 11:05:32
2014-06-15 19:21:55 Min_25
it seems that time limits are proportional to max {b}.
2012-12-28 17:29:29 Ashish Lavania
@Robert, what are the number of cases in the last test case?

Last edit: 2013-05-18 22:44:27
2012-12-09 14:05:23 Robert Gerbicz
To get AC you have to solve all input sets (these are very different difficulties)! My sample but somewhat optimized solution runs in 10 seconds.

Last edit: 2012-12-09 14:07:05
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.