# Practice on Toph

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

# Magic Number Count

By zobayer · Limits 1.5s, 1.0 GB

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

InputOutput
2
1 2
1 3
Case 1: 1
Case 2: 2

### Statistics

81% Solution Ratio

nnnnnnEarliest, 1M ago

ShafahidFastest, 0.3s

Sarwat.33Lightest, 13 MB

H_shafia4Shortest, 700B