You will be given two numbers A & B. Now you have to answer two things.
First number of prime numbers in the range of A and B(inclusive).
Second the sum of all possible subsets of prime numbers the range of A and B(inclusive).
As the sum can be very large output the sum modulo 10^9+7.
For Better understanding see the notes below the output section.
Input
The first line of the input is number of test cases T(T<=1000). Each of the next T lines will contain two numbers A & B (1<=A<=B<=1,00,000).
Output
For each test case print a line "Case P: Q R", where P is the case number, Q is the number of prime numbers in (A,B) and R is the subset sum of those prime numbers in(A,B).
Sample
| Input | Output |
|---|---|
2 1 2 1 5 | Case 1: 1 2 Case 2: 3 40 |
For this problem, we will consider the sum of empty set as Zero(0).
In the first case the only prime number in the range of 0 to 2 is 2. So number of prime number is 1.
And the two possible subsets : {2}, {}(empty). So the subset sum is 2.
In the second case the prime numbers in the range of 1 to 5 are 2,3,5. So number of prime number is 3.
And the Possible subsets are:
{2}
{3}
{5}
{2,3}
{2,5}
{3,5}
{2,3,5}
{}(empty).
So the total sum is= 2+3+5+(2+3)+(2+5)+(3+5)+(2+3+5)=40.
