SPNUMBER - Special Prime Number
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.Added by: | AVM |
Date: | 2019-03-11 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | St. Louis HOT LPC 2017 |