N Bits

How many different integers between A and B (including A and B) have exactly N bits of 1 in the two's complement representation? That's the question to be answered in this problem.

Example

The problem is pretty clear. For example, suppose A is 5, B is 14, and N is 2. If we look at the two's complement binary representation of the integers between 5 and 14 and identify those with exactly 2 one bits, we find that there are five such numbers (identified by the left-pointing arrows):

5 6 7 8 9

0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1

← ← ←

10 11 12 13 14

1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0

← ←

So the answer for this case would be 5. (All the high-order bits in these numbers are 0; they are not shown for clarity.)

Input Specification

There will be multiple input cases to consider. For each case there will be a single input line containing A, B, and N. The input for the last case will be followed by a line containing three zeroes. A and B will each be in the range –2 147 483 648 to +2 147 483 647, and N will be in the range 1 to 32.

Output Specification

For each input case, display the case number (1, 2, …) and the appropriate number. Display a blank line after the output for each case. The sample input and output illustrate the appropriate formats.

Sample Input

1. 5 14 2
2. 5 14 3
3. -1 1 1
4. 0 0 0

download as text file

Output for Sample Input

1. Case 1: 5 numbers
3. Case 2: 4 numbers
5. Case 3: 1 numbers

download as text file