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 TT (T1000T ≤ 1000), denoting the number of test cases.

Each test case start with an integer LL (0L1000000000 \le L \le 100000000) and UU (0U1000000000 \le U \le 100000000) where LL denoting the lower bound and UU denoting the upper bound. You assume that LUL \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 CC is the number of prime numbers within the given interval.

Sample

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

Discussion

Statistics


81% Solution Ratio

nnnnnnEarliest, 1M ago

ShafahidFastest, 0.3s

Sarwat.33Lightest, 13 MB

H_shafia4Shortest, 700B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.