Magic Number Count

Magic number is an integer number, which is only divisible by itself and total number of divisor will be 2.

Your task is to calculate the number of prime numbers from lower bound to upper bound inclusive.

Input

Input starts with an integer $T$ ($T ≤ 1000$), denoting the number of test cases.

Each test case start with an integer $L$ ($0 \le L \le 100000000$) and $U$ ($0 \le U \le 100000000$) where $L$ denoting the lower bound and $U$ denoting the upper bound. You assume that $L \le U$. You assume that one is not a prime.

Output

For each test case, print a line in the format, "Case T: C", where T is the case number and $C$ is the number of prime numbers within the given interval.

Sample

Input	Output
2 1 2 1 3	Case 1: 1 Case 2: 2