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

Limits: 1s, 512 MB

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

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

Discussion