“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).
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).
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).
Input | Output |
---|---|
4 1 4 2 2 1 5 4 4 | Case 1: 2 Case 2: 1 Case 3: 3 Case 4: 0 |