October 7 - BMTK Programming School, High League

How Many Ones Needed?

prb5492 To write binary numbers we need only two digits 0 and 1. To write a specific value we need a fixed number of ones, but of course number of zeros may vary because of leading zeros. For example to write values between 5 and 10 (inclusive) we need total 12 ones as shown in the figure on the left. You have to write a program that finds total number of ones that are required to write numbers in binary within a given range a and b.


Contains up to 100000 lines of input. Each line contains two integers a and b (0ab2 * 109). The last line contains two zeros and should not be processed.


For each input line produce one line of output. This line contains the serial of output followed by an integer which denotes the number of 1's required to write all the values between a and b (inclusive) in binary. Look at the output for sample input for details.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 10
20 30
0 0
Output example #1
Case 1: 12
Case 2: 35