AVM is a mathematician. Of course he likes to play with numbers. One day, AVM found a new number type called "Special Prime Number".

Special Prime Numbers is a number that obtained from the product of 2 distinct prime numbers. For example, six is a Special Prime Number from 2 and 3.

AVM became curious with the number type and he wanted to know the number of Special Prime Number between A and B inclusive.

Input

The input file consists of several lines. The first line contains an integer T as the number of test cases. The next T lines contain 2 integers A and B.

Output

The output file should contains T lines. The i-th line should contains Case #X: Y with X as the case number and Y as the answer of i-th case.

Constraint

1 <= T <= 1 000
1 <= A <= B <= 1 000 000

Example

Input:
3
1 10
11 20
21 30

Output:
Case #1: 2
Case #2: 2
Case #3: 3

Explanation

The Special Prime Numbers from 1 to 30 inclusive are: 6, 10, 14, 15, 21, 22, 26. Therefore, the answer of each cases are 2, 2, and 3 respectively.