“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).