High School Programming League Problems Archive

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.