Choto Chele and Dumb Numbers

nobody DIU-SWE Intra Department...
Limits 1s, 512 MB

“Choto Chele” loves natural numbers very much. He enjoys playing with numbers. He defines numbers with two types- "Smart" numbers & "Dumb" Numbers.

Numbers that are divisible by 1 and only that number is "Dumb" numbers and all the rest are "Smart" numbers.

3 is a Dumb number as it is only divisible by 1 and 3.

But 4 is a Smart number as it is divisible by 1, 2 and 4.

For your kind information, 1 is neither Dumb nor Smart. 1 is "Not so Dumb, Not so Smart" number.

“Choto Chele” has a sympathy for Dumb numbers and you have sympathy for “Choto Chele”. “Choto Chele” can't go very far by figuring out the Dumb numbers. “Choto Chele” knows that you are a good programmer and he wants your help.

He wants you to write a program that will take two numbers A & B and output the number of Dumb numbers in the range A & B (inclusive).

Input

The first line is the number of test case T (T<=10^6).

Each of the next T lines will contain two integer A and B (1<=A<=B<=10^5).

Output

For each test case print a line in “Case I: R” format where I is case number and R is the number of Dumb numbers in the range A and B (inclusive).

Sample

InputOutput
4
1 4
2 2
1 5
4 4
Case 1: 2
Case 2: 1
Case 3: 3
Case 4: 0

Submit

Login to submit.

Statistics

60% Solution Ratio
hamza05Earliest, Apr '18
mumith_fahim99Fastest, 0.1s
jinnatLightest, 18 MB
Tanveer2202Shortest, 519B
Toph uses cookies. By continuing you agree to our Cookie Policy.