# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Easiest Problem Ever

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).

### Samples

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.

Login to submit